Re: clojure.zip: skip a node
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 clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: clojure.zip: skip a node
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 clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: clojure.zip: skip a node
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 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 clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
clojure.zip: skip a node
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 clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com 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 clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
