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
On Tuesday, May 6, 2014 at 5:24:53 PM UTC+2, Pascal Germroth wrote:
>
>
> 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))))))
>
>
>>
>> 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
>>
>>
>> On Monday, May 5, 2014 6:01:04 PM UTC-5, Pascal Germroth wrote:
>>>
>>> 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
>>>
>>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
