Give this a go:
(defn ^:private walk-tree* [all seen to-do]
(when-let [[curr & others] to-do]
(if (contains? seen curr)
(recur all seen others)
(lazy-seq
(when-let [node (first (filter #(= (:v %) curr) all))]
(println node)
(cons curr
(walk-tree* all
(conj seen curr)
(concat others
(:parent node)))))))))
(defn walk-tree [all]
(walk-tree* all #{} [(-> all first :v)]))
I'm still not super happy with it, but it should solve your problem. The
basic trick is to not use things like `mapcat`, as you need to keep
updating some state (the `seen` map) between calls. The approach here is to
pass "work to be done" and "work to be ignored" together. Then both can be
kept up to date in sync with each other. Your recursion becomes a bit more
explicit, too.
I hope that helps!
On 7 July 2013 00:33, looselytyped <raju.gan...@gmail.com> wrote:
> Good morning everyone!
>
> I have a problem that I have been struggling with for a few days now. I
> have a directed acyclic graph that I am trying to walk, and can't seem to
> figure out a to prevent my walking already visited branches. Here is the
> code
>
> (def values
> [{:v "a" :parent ["b"]}
> {:v "b" :parent ["c"]}
> {:v "c" :parent ["d" "e"]}
> {:v "d" :parent ["f"]}
> {:v "e" :parent ["f"]}
> {:v "f"}])
>
> As you can see, I have a vector of records, each with a "value" and a
> vector of "parent"s. A node can have more than zero or more parents.
>
> a o
> |
> b o
> |
> c o
> |\
> d o o e
> |/
> f o
>
> Here is the fruits of several attempts ...
>
> (defn walk-tree
> ([values]
> (letfn [(in?
> [seq elm]
> (some #(= elm %) seq))
> (walk [already id]
> (when-not (in? already id)
> (when-let [n (some #(if (= id (:v %)) %) values)]
> (lazy-seq
> (cons (:v n)
> (mapcat #(walk (conj already (:v n)) %) (:parent
> n)))))))]
> (walk #{} (:v (first values))))))
>
> I was hoping to use the set as a way to record which nodes have been
> visited. Unfortunately as you might be able to tell, that's not going to
> work. The result of running this is
>
> ("a" "b" "c" "d" "f" "e" "f")
>
> Notice that "f" gets in the list twice. One way to do it would be to make
> a set out of it, but that eliminates the laziness aspect.
>
> Can anyone point me in the right direction here?
>
> Thanks,
>
> Raju
>
> --
> --
> 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.
>
>
>
--
--
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.
