Trie for auto-complete (or: how to implement auto-complete in 4 lines of Clojure)

trie.clj

(def t
  "trie containing the 100,000 most common english words"
  (with-open [r (clojure.java.io/reader "/tmp/words-100000")]
    (reduce #(assoc-in %1 %2 (sorted-map \0 nil)) (sorted-map) (line-seq r))))

(defn search [p m]
  "return a sorted sequence of all words in the trie m that start with the given prefix p"
  (let [n (get-in m p)
        next (mapcat #(search (str p (key %)) m) (dissoc n \0))]
    (if (contains? n \0) (cons p next) next)))

(time (search "trie" t))