深度优先使用clojure.walk索引任何Clojure表单

1> A. Webb..：

---

A walk是递归的,不提供累加器参数,这就是你不得不求助于更新原子的原因.

A zipper是迭代的,因此您可以携带其他信息而不会破坏功能模式.

自然深度优先遍历是一个预订遍历,但您是在下订单后,所以这需要一些额外的工作.

这是使用拉链的后订单遍历:

(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)])

---

@MarcusJuniusBrutus要处理其他表格,请查看`zipper`.我使用`zip-seq`作为这个基于测序的测试用例的快捷方式,但是`zipper`允许你指定什么构成一个分支及其子代.因此,您可以创建一个通用集合zipper以传递给此遍历后顺序函数.