I'm not sure if I fully understand what you want, but I find this sort
of thing is often cleanest using mutable data structures, i.e., (off
the top of my head, possibly buggy),
(defn visit
([node] (visit node (HashSet.)))
([node s]
(when-not (.contains s node)
(.add s node)
(lazy-cat (map #(visit % s) (get-children node)) [node]))))
Because this doesn't use reduce, it should still be lazy.
-Jason
> (defn visit [node]
> (lazy-cat (map visit (get-children node)) [node]))
On Feb 12, 2009, at 7:37 PM, Jeffrey Straszheim wrote:
> Sounds good. The one hitch is that I'm passing around a "visited"
> hash (I'm actually traversing a graph looking for spanning trees),
> so I end up calling (reduce XX [visited acc] (get-children node)) on
> the children, which (I think) kills the laziness.
>
> On Thu, Feb 12, 2009 at 10:18 PM, Jason Wolfe <[email protected]>
> wrote:
>
>
>
> On Feb 12, 4:01 pm, Jeffrey Straszheim <[email protected]>
> wrote:
> > It is easy to do a lazy preorder walk of a tree (in psuedo-clojure):
> >
> > (fn visit [node]
> > (lazy-cons node (map visit (get-children node))))
> >
> > So, that much is obvious. However, I cannot think of an obvious
> way to do a
> > post-order traversal lazily. I sort of assume it cannot be done,
> as the
> > whole point -- more or less -- of a post ordered walk is you've
> visited the
> > children already.
>
> I think
>
> (defn visit [node]
> (lazy-cat (map visit (get-children node)) [node]))
>
> should do more or less what you want. It won't be quite as lazy as
> the preorder, since it has to walk all the way to a leaf before it can
> start producing values, but I think it will evaluate just what's
> needed to produce each value (perhaps plus a little bit).
>
> -Jason
>
>
>
> >
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to [email protected]
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
-~----------~----~----~----~------~----~------~--~---
