That looks like it should work. This may be one of the cases where using a mutable structure behind the scenes is the right thing to do.
On Thu, Feb 12, 2009 at 10:45 PM, Jason Wolfe <jawo...@berkeley.edu> wrote: > 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 <jawo...@berkeley.edu>wrote: > >> >> >> >> On Feb 12, 4:01 pm, Jeffrey Straszheim <straszheimjeff...@gmail.com> >> 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 clojure@googlegroups.com 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 -~----------~----~----~----~------~----~------~--~---
