clojure

how to implement walk/postwalk traversal using clojure.zip


I can't figure out how to implement the clojure.walk/postwalk function using clojure.zip:

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

outputs:

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

Solution

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

    Edit: for prewalk, just perform the z/replace before going down.

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