Как реализовать пример автозаполнения в Clojure?

Question

Этот пост в блоге (http://williamedwardscoder.tumblr.com/post/18319031919/programming-language-readability) содержит реализацию автозаполнения в Haskell и Python для сравнения читабельности языков программирования.

Любопытно узнать, как реализовать то же самое в Clojure. Будут ли коды Clojure более читабельными из-за его большей способности к абстракции?

Answer 1

Минималистская реализация:

(ns trie.example)

(defn trie-add [trie & words]
  (reduce
   (fn [trie word]
     (assoc-in trie (concat word [::val]) word))
   trie
   words))

(defn trie-matches [trie prefix]
  (letfn [(search [node]
            (mapcat (fn [[k v]]
                      (if (= ::val k) [v] (search v)))
                    node))]
    (search (get-in trie prefix))))

Пример использования:

;; Create trie
(def trie (trie-add {} "foo" "ba" "bar" "baz" "qux" "quux"))

;; trie looks like this:
{\q
 {\u
  {\u {\x {:trie.example/val "quux"}},
   \x {:trie.example/val "qux"}}},
 \b
 {\a
  {\z {:trie.example/val "baz"},
   \r {:trie.example/val "bar"},
   :trie.example/val "ba"}},
 \f {\o {\o {:trie.example/val "foo"}}}}

;; Autocomplete
(trie-matches trie "ba")
=> ("baz" "bar" "ba")

Такие вещи, как сортировка, сохранение несловесных значений и сжатие, оставляются читателю в качестве упражнения.