clojure.zip: skip a node

[Pascal Germroth]

Hi,

I'm using clojure.zip to edit a tree by visiting each location using zip/next, possibly using zip/replace to alter the tree.

There are cases where I replace a part of the tree with another tree that will/must not be visited, but I couldn't find a good way to skip nodes, since

(zip/next (zip/replace loc new-subtree)) will walk right into my new tree, and I can't use (zip/right (zip/replace loc new-subtree)) as the replaced location might already be the rightmost.

Is there a built-in function I missed, or a zip enhancement library I could use?

(defn skip

  "returns the next location that is not a child of this one"

  [loc]

  (if (or (z/end? loc) (nil? loc))

    loc

    (loop [loc loc]

      (or (z/right loc)

          (recur (z/up loc))))))

I came up with this replacement, does that seem like a good idea, or am I using zip completely wrong (because what I really would like to do is iterate backwards through the tree, starting at the end, using zip/prev; but there's also no function to just jump to the end as far as I can tell)

Cheers,

-- 

pascal

[Alex Miller]

I wrote this article long ago which hints about this at the end:

https://www.ibm.com/developerworks/library/j-treevisit/

The approach I have taken for editing trees with zippers is to do a post-walk from end to beginning - that way you're always done transforming and will not walk into your edited subtrees. The article does talk a little about how to separate navigation from transformation; it's not particularly hard. You want to start from your rightmost node, which you can get from a repeated application of zip/rightmost or last of zip/rights. Then repeatedly call prev till you reach a node without a parent at that point convert the loc to a node in the termination.

I can dig up actual code for this later if you're interested.

Alex

[Pascal Germroth]

On Tuesday, May 6, 2014 4:07:11 PM UTC+1, Alex Miller wrote:

I wrote this article long ago which hints about this at the end:

https://www.ibm.com/developerworks/library/j-treevisit/

I started from that actually, very helpful article.

I have since noticed a bug in my previous skip function where it would loop infinitely when skipping from the rightmost location.

The fix includes an end function, so I can no just iterate backwards using that as you suggested.

Leaving this here for future reference, in case anybody comes across the same problem:

(defn end

  "returns the location loc where (end? (next loc)) is true."

  [loc]

  (loop [loc loc]

    (let [loc (z/rightmost loc)]

      (if (z/branch? loc)

        (recur (z/down loc))

        loc))))

(defn skip

  "returns the next location that is not a child of this one"

  [start-loc]

  (loop [loc start-loc]

    (cond

      ; can't skip, jump to end

      (nil? loc) (z/next (end start-loc))

      ; at end

      (z/end? loc) loc

      ; go to right/up

      true (or (z/right loc)

               (recur (z/up loc))))))

[Marco Rucci]

Hi all, thank for the helpful discussion.

I've stumbled upon the same issue of needing to skip a subtree during a traversal and solved it with the following skip function that is a slight modification of one in the original message:

(defn skip-subtree

  "Fast-forward a zipper to skip the subtree at `loc`."

  [loc]

  (cond

    (zip/end? loc) loc

    (some? (zip/right loc)) (zip/right loc)

    (some? (zip/up loc)) (recur (zip/up loc))

    :else (assoc loc 1 :end)))

In short, we traverse to the right if there's a right, otherwise we recursively go up and check again if there's a right.  If we never find a right, then we'll navigate back up to the root.  In this case, mark the zipper as consumed (with `:end`) and return.

Seems to be working well, so hopefully it can help somebody else. 

Cheers.

--

Marco