5

ネストされたベクトルとして表されるツリーがあります。indexedこのように各ノードのインデックスを表示して、ツリーの一般化を行いたいです。

(visit 42); => [0 42]
(visit [6 7]); => [0
              ;     [[0 6] 
              ;      [1 7]]]

ナイーブな実装はclojure.zipを直接使用します（すでにここで尋ねられているように）

(defn visit [tree]
  (loop [loc (vector-zip tree)]
    (if (end? loc)
      (root loc)
      (recur 
        (next (edit loc #(conj 
                           [(count (lefts loc))] 
                           %)))))))

ただし、を繰り返すとclojure.zip/next、事前順序トラバーサルが実行され、この場合は無限ループになります（未訪問のノードは無限conjに[:found]ベクトルになります）。別のアプローチはを使用することclojure.walk/postwalkですが、インデックスなどの構造情報を提供しません。

これをどのように実装しますか？postorder-nextすぐに解決するforzipはありますか？

4

1 に答える 1

4

あなたがやろうとしていることを理解しているかどうかはわかりませんが、例では、ノードに割り当てられたインデックスが左側の兄弟の数に対応していることを示唆しています (2 番目の例では、ルート ノードと6子の両方であるため)のラベルが付いてい0ます)。更新: どうやら私visitは最初のラウンドで例を読み違えただけのようです - それは意図を十分に明確にします... 幸いなことに、正しく読んだので、以下の答えが正しいようです。

それが正しければ、これは にclojure.walk/postwalk基づく解決策です。

(defn index-vec-tree [vt]
  [0 (walk/postwalk
       (fn [node]
         (if-not (vector? node)
           node
           (vec (map-indexed vector node))))
       vt)])

与えられた例では：

user> (index-vec-tree [6 7])
[0 [[0 6] [1 7]]]
user> (index-vec-tree 42)
[0 42]

更新:map-indexed (1.2 で利用可能; 1.1 でmap+を使用)を使用した簡単なソリューション:clojure.contrib.seq-utils/indexed

(defn index-vec-tree [vt]
  (letfn [(iter [i vt] [i (if (vector? vt)
                                (vec (map-indexed iter vt))
                                vt)])]
    (iter 0 vt)))
于 2010-07-30T19:28:34.293 に答える