Clojure: How to generate a 'trie'?

clojure, functional-programming, tree, trie

Solution

Here's a cleaned up solution. This fixes a bug Brian's add-to-trie method since it's currently dependent upon you inserting the seqs in increasing-length order. It also allows querying the trie by prefix, which is a common use case.

Note the memory usage here is higher since it stores the values in the leaf nodes of the trie so you can perform searches.

(defn add-to-trie [trie x]
  (assoc-in trie x (merge (get-in trie x) {:val x :terminal true})))

(defn in-trie? [trie x]
  "Returns true if the value x exists in the specified trie."
  (:terminal (get-in trie x) false))

(defn prefix-matches [trie prefix]
  "Returns a list of matches with the prefix specified in the trie specified."
  (keep :val (tree-seq map? vals (get-in trie prefix))))

(defn build-trie [coll]
  "Builds a trie over the values in the specified seq coll."
  (reduce add-to-trie {} coll))

Problem

Original source