Why isn't a zipper appropriate for tree recursion?
On Sunday, December 8, 2013 2:16:33 AM UTC, Alexander Hudek wrote:
>
> This is still just recursion because of the map. That means it has all the
> problems of recursion. If you need to avoid recursion, you need to do a
> depth first or breadth first traversal of the tree and hold onto state as
> you do it. The zipper does some of this for you and provides an easy way to
> traverse data in a depth first fashion. If you need additional state, say
> to collect data, or track data as you mutate the tree, then zip-visit may
> or may not help.
>
> Ultimately, to use a zipper you need to structure your algorithms to work
> with a depth first traversal rather than using tree recursion. That said,
> doing standard tree recursion may be the right answer. It all depends on
> your use case.
>
> On Wednesday, December 4, 2013 8:38:11 PM UTC-5, dabd wrote:
>>
>> Thanks I'll take a look at your libraries.
>> One problem I found with the zipper API is that if you have a recursive
>> function that takes a loc, when you call it on the clojure.zip/children of
>> a given loc it won't work because this function returns a seq of nodes
>> instead of a seq of locs. Shouldn't we add a function like
>> children-as-locs to the API for this purpose or is there another way?
>>
>> (defn children-as-locs
>> "Returns a seq of locs of the children of loc."
>> [loc]
>> (when (z/branch? loc)
>> (let [[node path] loc
>> cs (z/children loc)]
>> (map-indexed (fn [i c]
>> (with-meta [c {:l (vec (take i cs))
>> :pnodes (if path (conj (:pnodes path)
>> node) [node])
>> :ppath path
>> :r (vec (drop (inc i) cs))}]
>> (meta loc)))
>> cs))))
>>
>> On Wednesday, December 4, 2013 11:46:29 PM UTC, Alexander Hudek wrote:
>>>
>>> Additionally, if you need more complex access patterns you could see if
>>> this helps:
>>>
>>> https://github.com/akhudek/zip-visit
>>>
>>> For performance, there is a fast-zip library that is api compatible with
>>> clojure.zip. You can just swap the clojure.zip namespace for the fast-zip
>>> namespace. Note that you'd need to make the same swap in any libraries you
>>> use with your zippers (like zip-visit) since fast-zip is not implementation
>>> compatible with clojure.zip.
>>>
>>> More broadly, I've found that straight up recursive algorithms can be a
>>> lot faster than zippers, especially for read only operations. Of course the
>>> stack size limits what you can do with tree recursion. As others have said,
>>> it's best to see if you actually have performance problems first.
>>>
>>> On Wednesday, December 4, 2013 5:30:02 PM UTC-5, James Reeves wrote:
>>>>
>>>> On 4 December 2013 21:09, dabd <dario....@gmail.com> wrote:
>>>>
>>>>> I didn't get there because I ran into problems with the zipper API.
>>>>> When you call 'children' on a loc you get a seq of nodes instead of a
>>>>> seq
>>>>> of locs which causes me problems in a recursive algorithm operating on
>>>>> locs.
>>>>>
>>>>
>>>> Have you tried using next and end? for a depth-first transversal?
>>>>
>>>> - James
>>>>
>>>
--
--
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/groups/opt_out.
