Clojure: Comment générer une «trie»?

comme une approche générale, voici ce que je ferais:

• Écrivez quelques fonctions pour créer une trie et insérer de nouveaux éléments dans une trie.
• créer une nouvelle trie.
• Itérate à travers la liste d'entrée et insérez chaque élément dans la trie.

  Ce problème se prête très bien à une mise en œuvre récursive. Je viserais cela si possible.

Je suis sûr qu'il y a une manière plus jolie (il y avait! Voir la réponse de Brian It c'est mieux):

(defn find-in-trie
  "Finds a sub trie that matches an item, eg:
  user=> (find-in-trie '(1 (2) (3 (2))) 3)
  (3 (2))"
  [tr item]
  (first (for [ll (rest tr) :when (= (first ll) item)] ll)))


(defn add-to-trie
  "Returns a new trie, the result of adding se to tr, eg:
  user=> (add-to-trie nil '(1 2))
  (1 (2))"
  [tr se]
  (cond
    (empty? se) tr
    (empty? tr) (add-to-trie (list (first se)) (rest se))
    :else (if-let [st (find-in-trie tr (first se))]
            (cons (first tr)
                  (cons (add-to-trie st (rest se))
                        (filter (partial not= st) (rest tr))))
            (cons (first tr)
                  (cons (add-to-trie (list (first se)) (rest se))
                        (rest tr))))))

(def in '((1 2)
          (1 2 3)
          (1 2 4 5 9)
          (1 2 4 10 15)
          (1 2 4 20 25)))

(reduce add-to-trie '(nil) in)

Les listes sont très maladroites ici, sans parler d'inefficace. Dans Clojure, il est plus idiomatique d'utiliser des vecteurs et des cartes de hachage et des ensembles le cas échéant. Utilisation de Hash-Maps:

user> (def trie (reduce add-to-trie {} in-tree))
#'user/trie
user> trie
{1 {2 {4 {20 {25 {:terminal true}}, 10 {15 {:terminal true}}, 5 {9 {:terminal true}}}, 3 {:terminal true}, :terminal true}}}
user> (in-trie? trie '(1 2))
true
user> (in-trie? trie '(1 2 4))
nil
user> (in-trie? trie '(1 2 4 20 25))
true