When you iterate through an arbitrarily nested Clojure zipper in a depth-first fashion via z/next, can you get or reconstruct the already visited part of the zipper, preserving its structure? For example, let's have a vector zipper of [0 [1 2] 3]. How can I implement a function visited to return the visited part of the zipper, such as [0 [1]] when visiting 1?
EDIT: Prompted by the helpful answers, I realized that a loc can be considered visited only when its subtree is completely traversed. Consequently, only non-branch locs (i.e. (complement z/branch?)) count as visited.
(require '[clojure.zip :as z])
(def zipper (z/vector-zip [0 [1 2] 3]))
(defn visited
[zipper]
; ...
)
(-> zipper z/next visited)
; => [0]
(-> zipper z/next z/next visited)
; => [0]
(-> zipper z/next z/next z/next visited)
; => [0 [1]]
(-> zipper z/next z/next z/next z/next visited)
; => [0 [1 2]]
(-> zipper z/next z/next z/next z/next z/next visited)
; => [0 [1 2] 3]
z/lefts returns only the visited part on the same hierarchical level.
EDIT 2: The answer by amalloy seems to almost work. If we make it start with into, then it works correctly for the example zipper:
(def visited
(letfn [(root? [node]
(= (z/node node) (z/root node)))]
(fn [node]
(if-let [parent (z/up node)]
(let [comb-fn (if (root? parent) into conj)]
(comb-fn (visited parent)
(if (z/branch? node)
(vec (z/lefts node))
(conj (vec (z/lefts node)) (z/node node)))))
[])))) ;; we're at the root
However, its limitations become apparent with more nesting. For example:
(def zipper (z/vector-zip [0 [1 [2]]]))
(-> zipper z/next z/next z/next z/next z/next visited)
; => [0 [1] [2]]
I wonder if z/edit can fit better.
If I understand your objective properly I believe this will do the trick:
(defn visited [loc]
(loop [cur loc
start true]
;; Loop from the starting location up to the root
(if-let [par (z/up cur)]
(recur
;; Replace our parent with a node that only includes its visited children
(z/replace
par
(z/make-node
par
(z/node par)
(cond-> (z/lefts cur)
;; If we started at a branch, don't treat its children as visited
(not (and start (z/branch? cur))) (concat [(z/node cur)]))))
false)
(if (and start (not (z/end? cur)))
[]
(z/node cur)))))
As a test, here is an example of printing the return from visited for each step in a traversal of a relatively complex tree:
(def root (z/vector-zip [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10 11]]))
(loop [loc root]
(when (not (z/end? loc))
(println "visit " (z/node loc))
(println "visited " (visited loc))
(recur (z/next loc))))
visit [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10 11]]
visited []
visit [1 [2 3 4] 5]
visited []
visit 1
visited [[1]]
visit [2 3 4]
visited [[1]]
visit 2
visited [[1 [2]]]
visit 3
visited [[1 [2 3]]]
visit 4
visited [[1 [2 3 4]]]
visit 5
visited [[1 [2 3 4] 5]]
visit 6
visited [[1 [2 3 4] 5] 6]
visit [[[7 8] [9]] 10 11]
visited [[1 [2 3 4] 5] 6]
visit [[7 8] [9]]
visited [[1 [2 3 4] 5] 6 []]
visit [7 8]
visited [[1 [2 3 4] 5] 6 [[]]]
visit 7
visited [[1 [2 3 4] 5] 6 [[[7]]]]
visit 8
visited [[1 [2 3 4] 5] 6 [[[7 8]]]]
visit [9]
visited [[1 [2 3 4] 5] 6 [[[7 8]]]]
visit 9
visited [[1 [2 3 4] 5] 6 [[[7 8] [9]]]]
visit 10
visited [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10]]
visit 11
visited [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10 11]]
nil