On Sun, Jun 13, 2010 at 8:39 AM, Oleg <oleg.richa...@gmail.com> wrote:
> Thank you, but could you provide me a little code snippet which will
> iterate through collection and assoc "children" key for each row.
>
> On 13 июн, 16:35, Andrzej <ndrwr...@googlemail.com> wrote:
>> On Sun, Jun 13, 2010 at 7:35 PM, Oleg <oleg.richa...@gmail.com> wrote:
>>
>> > Currently i'm just calling function, but there is a danger of
>> > StackOverflow. I can't use recur, because it's not last statement. As
>> > i can understand recur is good to build long sequences, but in my case
>> > i'm building hierarchy.
>>
>> Two potential solutions:
>> 1. Build a lazy hierarchy, i.e. instead of returning a nested
>> structure, return a function that produces it. It might be better to
>> use a built-in function tree-seq though (check the implementation of
>> file-seq and xml-seq).
I think a lazy hierarchy is the way to go, but tree-seq is a way
to walk a tree, not build one.
For a "real" example of a lazy hierarchy, you can look at
clojure.contrib.lazy-xml, which builds a lazy tree of XML nodes.
But it may be hard to learn from without getting lost in SAX API
craziness, so here's an attempt at a simpler example:
First, a function to return some children for a given parent:
(defn children [parent]
(vec (map + (repeat (* 10 parent)) (range 10))))
(children 42)
;=> [420 421 422 423 424 425 426 427 428 429]
Note this is a vector and thus non-lazy, just as in your problem
description.
Now we want a function that returns a tree node for a given item.
For this example a node will be just a map with an :item and
a lazy sequence of :kids:
(defn node [item]
{:item item
:kids (map node (children item))})
The fact that 'map' is lazy is critical here. If we force that
map when creating a node, our first call to 'node' will force the
whole tree and could have unbounded recursion. But 'map' is lazy
so we know that a single call to node will be O(1). Only when we
actually realize the :kids seq will 'children' be called.
We can now build a tree and look something up in it:
(-> (node 0) :kids (nth 3) :kids (nth 5) :kids (nth 8) :item)
;=> 358
So this is an infinitely deep tree that we can navigate without
any actual recursion, just as we can walk an infinite lazy seq
without recursion, and thus there's no threat that the stack will
overflow:
(:item (reduce #(nth (:kids %1) %2)
(node 0)
(take 5000 (cycle (range 10)))))
;=> 123456789012345678...67890123456789
Note that since these trees are infinitely deep, a depth-first
walk like tree-seq does is probably not very useful:
(take 8 (map :item (tree-seq :kids :kids (node 1))))
;=> (1 10 100 1000 10000 100000 1000000 10000000)
Hope that helps!
--Chouser
http://joyofclojure.com/
--
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
