8

次のツリー（またはマップやベクトルを含むClojureの他のフォーム）があるとします。

'( (a b) (c d) )

フォーム全体の深さ優先走査に従って各サブフォームにインデックスを付け、フォームの子（存在する場合）のインデックスのベクトル（またはリスト）も提供するマップをClojureで生成したいと思います。

0 -> a []
1 -> b []
2 -> (a b) [0 1]
3 -> c []
4 -> d []
5 -> (c d) [3 4]
6 -> ( (a b) (c d) ) [2 5]

私はこれまでclojure.walkを使用して最初の部分（サブフォームのインデックス付け）を作成することしかできませんでしたが、子のインデックスを生成する方法についても困惑しています。私のコードは最後に追加され、次のように生成されます。

user=> (depthFirstIndexing '( (a b) (c d) ))
{6 ((a b) (c d)), 5 (c d), 4 d, 3 c, 2 (a b), 1 b, 0 a}

したがって、サブフォームのインデックスは深さ優先走査に従って正しく生成されますが、すべてのサブフォームの子のインデックスを取得する方法がわかりません。zippersモジュールを使用しようとしましたが、インデックスを収集するために深さ優先走査を実行する方法がわかりませんでした。

途中のコード

(use 'clojure.walk)
(defn depthFirstIndexing [aform]
  (let [counter       (atom -1)
        idxToSubform  (atom {})
        ]
    (postwalk (fn [x]
                (def idx (swap! counter inc))
                (swap! idxToSubform assoc idx x)
                x)
    aform)
  @idxToSubform))
4

2 に答える 2

8

Awalkは再帰的であり、アキュムレータ引数を提供しません。そのため、アトムの更新に頼らざるを得ませんでした。

Azipperは反復的であるため、機能パターンを壊すことなく他の情報を運ぶことができます。

自然な深さ優先トラバーサルはプレオーダートラバーサルですが、ポストオーダー後なので、これには少し余分な作業が必要です。

これは、ジッパーを使用した注文後のトラバーサルです。

(require '[clojure.zip :as z])

(defn dfs-post-order-traversal [zipper]
  (loop [loc zipper, a []] 
    (cond 
      (z/end? loc) 
        (conj a (z/node loc))
      (z/branch? loc) 
        (recur (z/next loc) a)
      :else
        (recur 
          (z/next loc) 
          (into 
            (conj a (z/node loc)) 
            (reverse 
              (drop 
                ((fnil count [nil]) (z/path (z/next loc))) 
                (z/path loc))))))))

そしてテストケース：

(dfs-post-order-traversal (z/seq-zip '((a b) (c d))))
=> [a b (a b) c d (c d) ((a b) (c d))]

リクエストを完了するには、ツリーの場所をインデックスにマップする必要があります。

(defn dfs-post-order-indexing [branch? children root]
  (let [pot (dfs-post-order-traversal (z/zipper branch? children conj root))
        m (zipmap pot (range))]
    (for [n pot] [(m n) n (if (branch? n) (map m (children n)) (list))])))

(dfs-post-order-indexing seq? identity '((a b) (c d)))
=>  ([0 a ()]
     [1 b ()]
     [2 (a b) (0 1)]
     [3 c ()]
     [4 d ()]
     [5 (c d) (3 4)]
     [6 ((a b) (c d)) (2 5)])

もっとエキゾチックなもの：

(dfs-post-order-indexing coll? seq [{:a :b :c :d} :e [:f [:g '(:h :i)]]])
=>  ([0 :a ()]
     [1 :b ()]
     [2 [:a :b] (0 1)]
     [3 :c ()]
     [4 :d ()]
     [5 [:c :d] (3 4)]
     [6 {:a :b, :c :d} (2 5)]
     [7 :e ()]
     [8 :f ()]
     [9 :g ()]
     [10 :h ()]
     [11 :i ()]
     [12 (:h :i) (10 11)]
     [13 [:g (:h :i)] (9 12)]
     [14 [:f [:g (:h :i)]] (8 13)]
     [15 [{:a :b, :c :d} :e [:f [:g (:h :i)]]] (6 7 14)])
于 2013-02-14T04:04:36.390 に答える
2 
(use '[clojure.walk :only (postwalk)])
(use '[clojure.set :only (map-invert)])

(defn idx [col]
  (let [m (map vector 
               (range) 
               (let [v (atom [])]
                 (postwalk (fn [f] (swap! v conj f) f) col) 
                 @v))
        rm (map-invert m)]
    (into {} (map (fn [[i e]]
                    [i [e (if (sequential? e) 
                            (mapv rm e)
                            [])]])
                  m))))

(idx '((a b) (c d)))
=> {0 [a []],
    1 [b []],
    2 [(a b) [0 1]],
    3 [c []],
    4 [d []],
    5 [(c d) [3 4]],
    6 [((a b) (c d)) [2 5]]}
于 2013-02-14T03:43:50.857 に答える