如何使用clojure.zip实现walk/postwalk遍历

Question

我不知道如何使用clojure.zip实现clojure.walk/postwalk功能：

(clojure.walk/postwalk
   #(do (println %)
        %)
   [1
    [2 [3 4 5]]
    [6 [7 8]]])

输出：

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

Answer 1

(defn postwalk [f loc]
  (let [loc (if-some [loc (z/down loc)]
              (loop [loc loc]
                (let [loc (postwalk f loc)]
                  (if-some [loc (z/right loc)]
                    (recur loc)
                    (z/up loc))))
              loc)]
    (z/replace loc (f (z/node loc)))))

=> (postwalk #(doto % prn) (z/vector-zip [1 [2 [3 4 5]] [6 [7 8]]]))
1
2
3
4
5
[3 4 5]
[2 [3 4 5]]
6
7
8
[7 8]
[6 [7 8]]
[1 [2 [3 4 5]] [6 [7 8]]]

编辑：对于预走，只需在下楼之前执行

z/replace

即可。

(defn prewalk [f loc]
  (let [loc (z/replace loc (f (z/node loc)))]
    (if-some [loc (z/down loc)]
      (loop [loc loc]
        (let [loc (prewalk f loc)]
          (if-some [loc (z/right loc)]
            (recur loc)
            (z/up loc))))
      loc)))

Answer 2

我相信有一种更惯用的方法来实现后序遍历，保留拉链式导航：

(defn post-zip
  [loc]
  ;; start from the deepest left child
  (loop [loc loc]
    (if-let [l (and (z/branch? loc) (z/down loc))]
      (recur l)
      loc)))

(defn post-next
  [loc]
  (if-let [sib (z/right loc)]
    ;; if we have a right sibling, move to it's deepest left child
    (post-zip sib)
    ;; If there is no right sibling move up if possible
    (if-let [parent (z/up loc)]
      parent
      ;; otherwise we are done
      (with-meta [(z/node loc) :end] (meta loc)))))

这允许您像使用普通拉链一样进行条件修改（即您不必总是这样做

z/replace

，有时您可以只调用

post-next

而不更改当前节点）。

考虑到这些辅助函数，postwalk 的实现变得相当简单：

(defn postwalk [f zipper]
  (loop [loc (post-zip zipper)]
    (if (z/end? loc)
      loc
      (recur (post-next (z/replace loc (f (z/node loc))))))))

此解决方案还具有不引入可能导致大型树堆栈溢出的递归的优点。