を反復ツリー

Question

はじめ

次の関数は、反復的にネストされたベクトルで作られたツリー構造をトラバースからトライを構築します。それは述語に対して各リーフをテストします。その真理テストに合格したすべての葉への道はTrie structureに返されます。後では、見つけられたすべてのパスが重複しない方法で記述されます。

(defn get-trie-of-matches [is? tree] 
    (loop [[tree i path fk] [tree 0 [] nil] 
     accum {}] 
    (cond 
     (>= i (count tree)) ;; end of level/go up 
     (if (nil? fk) accum (recur fk accum)) 

     (vector? (tree i)) ;; level down 
     (recur [(tree i) 0 (conj path i) [tree (inc i) path fk]] accum) 

     (is? (tree i)) ;; match 
     (let [new-accum (assoc-in accum (conj path i) {})] 
     (recur [tree (inc i) path fk] new-accum)) 

     :else ;; next on same level 
     (recur [tree (inc i) path fk] accum)))) 

さらに詳しい説明は、this postを参照してください。

例

述語としてeven?を使用して、関数に適用下記ツリー

(def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]]) 

を検討：

(get-trie-of-matches even? tree) 
=> {2 {3 {0 {}, 1 {}}}, 4 {0 {}}} 

結果が偶数にするために3つの経路を記述しtree。即ち、2-3-0,2-3-1及び4-0である。

問題

上記の機能が動作しても、ツリーを横断しながら、トライを構築するためのより良い方法があるかもしれません。現時点では、ハッシュマップがフラッディングされます。 assoc-inを介して各試合で。このアルゴリズムは、ツリー構造をレベルごとに相対的に横断しますが、各パスをグローバルな方法でaccumに接続しますが、これは必須ではありません。また、このメソッドはハッシュマップが使用されるためのみ可能です。それ以上の反復を容易にするために、Trieのシーケンシャルなデータ構造を使用する方がよいでしょう。これは上記の方法には適用できませんでした。トライは、ハッシュマップ固有の「グローバル」「書き込み」の機能に依存することなく、上記の関数get-trie-of-matches内から作成することができますどのように

質問

？

Answer 1

私はclojureのwalk apiを見てみることを提案します。

ネストしたコレクションに関数を再帰的に適用することができます。

user> (require '[clojure.walk :as w]) 
user> (w/postwalk-demo [1 3 [4 [6] 7] [[8]]]) 
Walked: 1 
Walked: 3 
Walked: 4 
Walked: 6 
Walked: [6] 
Walked: 7 
Walked: [4 [6] 7] 
Walked: 8 
Walked: [8] 
Walked: [[8]] 
Walked: [1 3 [4 [6] 7] [[8]]] 

[1 3 [4 [6] 7] [[8]]] 

重要なことは、あなたがすべてのステップで任意の項目を置き換えることができます：：ここで

user> (w/postwalk #(if (coll? %) (reverse %) (inc %)) 
        [1 3 [4 [6] 7] [[8]]]) 

(((9)) (8 (7) 5) 4 2) 

我々はすべての数字をインクリメントし、すべてのコレクションを逆に、維持するあなたはpostwalkを使用することができます。この場合 ネストされた構造。

あなたの仕事に今適用してください： あなたのツリーを歩いて、偶数番号のインデックスを保持しています。偶数を含むコレクションではなく、空のコレクション）：REPLで

;; helper function 
(defn empty-coll? [item] 
    (and (coll? item) (not (seq item)))) 

(defn make-trie [pred tree] 
    (w/postwalk 
    #(if (coll? %) 
     (keep-indexed (fn [idx item] 
         (cond (empty-coll? item) nil 
          (coll? item) (list idx item) 
          item idx 
          :else nil)) 
        %) 
     (pred %)) 
    tree)) 

：

user> (def tree [7 9 [7 5 3 [4 6 9] 9 3] 1 [2 7 9 9]]) 
#'user/tree 

user> (make-trie even? tree) 
((2 ((3 (0 1)))) (4 (0))) 

user> (make-trie #(> % 7) tree) 
(1 (2 ((3 (2)) 4)) (4 (2 3))) 

構造があなたのマップに似ています。 [死霊]（http://nathanmarz.com/blog/functional-navigational-を見てください

(defn make-trie-map [pred tree] 
    (w/postwalk 
    #(if (coll? %) 
     (into {} 
      (keep-indexed (fn [idx item] 
          (cond (empty-coll? item) nil 
            (coll? item) {idx item} 
            item {idx {}} 
            :else nil)) 
          %)) 
     (pred %)) 
    tree)) 

user> (make-trie-map even? tree) 
{2 {3 {0 {}, 1 {}}}, 4 {0 {}}}