在Clojure中获取一棵树的钥匙链 [英] get key-chains of a tree in Clojure

问题描述

我想从每根到每一个假都得到一棵树的钥匙链。

I wanted to get key-chains of a tree, from every root to every leave.

例如输入树：

{"b" {:term true}, "a" {"y" {:term true}, "x" {:term true}}}

我期望的输出是：

(("b" :term) ("a" "x" :term) ("a" "y" :term)) or ["b" "ax" "ay"]

我想出了一个尾递归，它很好用：

I've figured out a tail-recursion, it worked fine:

(defn down-strings [trie] 
  "this one works. 80msecs for address.txt, not bad at all"
  (lazy-seq 
    (loop [strings [],trie trie] 
      (if (empty? trie) strings
        (let [[k v] (first trie)] 
          (recur (if (:term v) (conj strings k) strings)
                 (reduce 
                   conj 
                   (rest trie)
                   (map (fn [[dk dv]] [(str k dk) dv]) (dissoc v :term)))))))))

现在我遇到麻烦了与我的记录紧急练习：

Now I have trouble with my recursive practice:

(defn down-strings [trie]
  (if (map? trie)
      (map (fn [[k v]] (conj (down-strings v) k)) trie)
      []))

输出为：

(("b" [:term]) ("a" ("y" [:term]) ("x" [:term])))

我已尽一切努力，无法解决此问题。

I tried everything I could, couldn't fix this.

推荐答案

(defn down-strings [trie]
  (mapcat
    (fn [[k v]]
      (if (map? v) (map (partial str k) (down-strings v)) [""]))
    trie))

例如，

(down-strings {"b" {:term true}, "a" {"y" {:term true}, "x" {:term true}}})
;("ax" "ay" "b")

我希望它比 @noisesmith的解决方案要慢很多。

I expect this to be quite a bit slower than @noisesmith's solution.

这篇关于在Clojure中获取一棵树的钥匙链的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！