1

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.

Improve this question

4 Answers 4

Reset to default
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
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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.

Improve this answer

1 Comment

Thank you for catching the poor formulation of my question! Indeed, what I want is to get the visited part only for non-branch locs. I don't think a branch can be considered visited unless its subtree is completely traversed.
1

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)))))))
Improve this answer

1 Comment

This almost works. If we make this start with into instead of conj (see above my edited question), it correctly traverses the example zipper. However, it fails with more nested data structures.
-1

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.

Improve this answer

3 Comments

If I read this correctly, it doesn't preserve the structure of the visited tree.
There are several approaches one could take to output a truncated tree. Can you describe the motivation for the problem?
For example, it can be used to reveal a part of a web page (i.e. Hiccup) up to a given point.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.