How to get the part of a Clojure zipper already visited in depth-first traversal?

Question

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.

Answer 1

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

Answer 2

Not easily. You want as output the value [0 [1 2]], but that value was never visited. So, you can't get it just by looking at any previously visited node. Instead, you will have to figure out a way to create this structure yourself based on examining the history of the visitor.

This doesn't sound impossible, but the algorithm is not entirely obvious. My first objection is that the problem seems poorly defined: do you really want the "already visited set" to shrink as you visit things? You say that when visiting [1 2] you consider the already-visited part to be [0 [1 2]], implying that while you're looking at the vector [1 2] you consider all of its contents to be already visited. In that case, while you're looking at the root, the entire tree is already visited, and as you descend into it, it becomes less and less visited!

So I would suggest ironing out a more exact definition of what you want, and hopefully if you are rigorous enough about it an algorithm will suggest itself.

Answer 3

Not a direct answer using Zippers, but you can solve this problem fairy easily using the Tupelo Forest library. Here is an example:

(dotest-focus ; walk the tree and keep track of all the visited nodes
  (hid-count-reset)
  (with-forest (new-forest)
    ; an "hid" is like a pointer to the node
    (let [root-hid (add-tree-hiccup [:a
                                     [:b
                                      [:c 1]]
                                     [:d
                                      [:e 2]]])
          tgt-hid  (find-hid root-hid [:** :c]) ; hid of the :c node we want to stop at
          state-atom    (atom {:visited-hids []
                          :found-tgt?   false})
          enter-fn (fn [path] ; path is from root
                     (let [curr-hid (xlast path)] ; curr node is last elem in path
                       (swap! state-atom
                         (fn [curr-state]
                           (cond-it-> curr-state
                             (falsey? (grab :found-tgt? it)) (update it :visited-hids append curr-hid)
                             (= curr-hid tgt-hid) (assoc it :found-tgt? true))))))]
      (newline)
      (println "Overall Tree Structure:")
      (spy-pretty (hid->tree root-hid))
      (newline)
      (walk-tree root-hid {:enter enter-fn}) ; accum results => state atom
      (newline)
      (println "final state map")
      (spyx @state-atom)
      (newline)
      (let [depth-first-tags (it-> (grab :visited-hids @state-atom)
                               (mapv hid->node it)
                               (mapv #(grab :tag %) it))]
        (is= depth-first-tags [:a :b :c])
        (println "depth-first tags thru target:")
        (println depth-first-tags)
        (newline)))))

with output:

Overall Tree Structure:
{:tag :a,
 :tupelo.forest/kids
 [{:tag :b,
   :tupelo.forest/kids [{:tupelo.forest/kids [], :tag :c, :value 1}]}
  {:tag :d,
   :tupelo.forest/kids [{:tupelo.forest/kids [], :tag :e, :value 2}]}]}


final state map
(clojure.core/deref state) => {:visited-hids [1005 1002 1001], :found-tgt? true}

depth-first tags thru target:
[:a :b :c]

Ran 1 tests containing 1 assertions.
0 failures, 0 errors.

Depending on your exact use-case, you can massage the output format as needed.

Answer 4

Your remark that "z/lefts returns only the visited part on the same hierarchical level" suggests its own solution. Call z/lefts, and then go up a level with z/up, and continue recursively.

I have a sketch worked out that is not exactly correct, but is close to having the right shape and illustrates what I'm suggesting:

(defn visited [node]
        (let [parent (z/up node)]
          (if (nil? parent)
            [] ;; we're at the root
            (conj (visited parent) 
                  (if (z/branch? node)
                     (vec (z/lefts node))
                     (conj (vec (z/lefts node)) (z/node node)))))))