Clojure, ассоциация в Okasaki Trie с использованием рекур

Question

Я наивно реализовал три слова из книги Окасаки «Чисто функциональные структуры данных» в Clojure. Просто для учебных целей, потому что, вероятно, нет никакой реальной выгоды, поскольку Clojure использовал более эффективный трюк под капотом карт нормалей, верно? Есть одна вещь, которая все еще беспокоит меня: trie-assoc не использует recur. Как я могу сделать рефакторинг, чтобы он делал только рекурсивный вызов на хвосте, используя recur? У меня такое чувство, что я мог бы использовать для этого молнии, но я пока не особо разбирался в молниях. Еще одна вещь, которая может быть улучшена, - это (если (пустой? Ключ) ...) с последующей деструктуризацией ключа. Может ли это быть более кратким?

(ns okasaki-trie.core)

(def empty-trie {:value nil :nodes nil})

(defn trie-get [key trie]
  (if (empty? key) (get trie :value)
      (let [[k & ks] key]
        (recur ks (get-in trie [:nodes k])))))

(defn trie-assoc [key val trie]
  (if (empty? key) (assoc trie :value val) 
      (let [[k & ks] key
            sub-trie-k (or (get-in trie [:nodes k]) empty-trie)
            sub-trie-k-new (trie-assoc ks val sub-trie-k)]
        (assoc-in trie [:nodes k] sub-trie-k-new))))

;;(def first-trie (trie-assoc "a" 3 empty-trie))
;;first-trie => {:nodes {\a {:nodes nil, :value 3}}, :value nil}

;;(def second-trie (trie-assoc "ab" 5 first-trie))
;;second-trie => {:nodes {\a {:nodes {\b {:nodes nil, :value 5}},
;;:value 3}}, :value nil}

;;(def third-trie (trie-assoc "b" 2 second-trie))
;;third-trie  => {:nodes {\b {:nodes nil, :value 2}, \a {:nodes {\b
;;{:nodes nil, :value 5}}, :value 3}}, :value nil}

;;(trie-get "b" third-trie)  ;=> 2
;;(trie-get "ab" third-trie) ;=> 5
;;(trie-get "abc" third-trie)  ;=> nil

Answer 1

Я не углублялся в этот алгоритм, но сомневаюсь, что хвостовая рекурсия возможна (полезно). Вам нужно пройтись по дереву, а затем создать резервную копию, чтобы восстановить узлы на пути к корню. Для этого требуется стек, следовательно, нет recur.

Если вы хотите, вы можете управлять своим собственным «стеком» в куче, сохраняя список родительских узлов и вручную возвращая их обратно в корень. Тогда вы можете использовать recur и избежать переполнения стека, но вы не будете использовать меньше памяти (вероятно, больше, на самом деле). Так что это только полезный трюк, если у вас есть деревья с 2 ^ 1000 элементов в них (и я, скорее, сомневаюсь, что вы делаете).

Редактировать

только что заметил ваш вопрос по поводу

(if (empty? key)
  (...empty...)
  (let [[k & ks] key]
    (...more...)))

Вы можете переписать это более просто и кратко, как:

(if-let [[k & ks] (seq key)]
  (...more...)
  (...empty...))

Answer 2

Я знаю, что это и некромантия, и немного не по теме, но я натолкнулся на этот вопрос, исследуя реализацию три в Clojure. Я был вынужден привязать к реализации с неизменностью. Вот решение, которое я придумал:

(def  trie (atom {}))
(defn key-list     [s    ] (into [] (map str s)))
(defn trie-add     [t k v] (assoc-in t (conj (key-list k) :v) v))
(defn trie-query   [t k  ] (get-in (deref t) (conj (key-list k) :v)))
(defn trie-subtree [t k  ] (get-in (deref t) (key-list k)))

, которая обеспечивает удивительно чистую реализацию, поэтому я хотел бы поделиться.

Для разведки и вставки:

(swap! trie trie-add "aac" 1)
(swap! trie trie-add "abc" 4)
(swap! trie trie-add "ab" 5)
(swap! trie trie-add "oaailfnalieuhkakjdfkjh" 1)
(swap! trie trie-add "aaailfnalieuhkakjdfkjh" 1)
(swap! trie trie-add "oaailfnalieancbnwiuybw" 1)
(swap! trie trie-add "oa" 3)

(trie-query trie "ab")
(trie-query trie "abc")
(trie-query trie "oaailfnalie")
(trie-query trie "oa")
(trie-query trie "oaailfnalieuhkakjdfkjh")

(trie-subtree trie "oa")
(trie-subtree trie "a")
(trie-subtree trie "oaailfnalieancbnwiuyb")
(trie-subtree trie "oaailfnalieancbnwiuy")
(trie-subtree trie "oaailfnalieancbnwiu")

(deref trie)

хорошие времена. Может быть, это отвечает на вопрос «Может ли это быть более кратким»?