Sorry, I wrote that implementation off-the-cuff and then realized that breadth-first search doesn't actually give you an appropriate dependency ordering. In the above examples I gave, I had: => (all-dependencies 30) (0 1 3 2 5 6 7 10 12 20 15 25 30) which isn't right because 20 depends on 15 which doesn't come before 20 in the list.
You want to do depth-first search, adding nodes in post-traversal order. There are several ways of going about this; here is one way that will hopefully be clear: (defn all-dependencies [n] (loop [stack [] unprocessed [n] processed {}] (if (empty? unprocessed) stack (let [i (peek unprocessed) status (processed i)] (case status :done (recur stack (pop unprocessed) processed), :seen-once (recur (conj stack i) (pop unprocessed) (assoc processed i :done)), (recur stack (into unprocessed (dependencies i)) (assoc processed i :seen-once))))))) Items start out in `unprocessed` and eventually get added to the `stack` accumulator which holds the final dependency list. (I called it `stack` because, essentially, you're building the "call stack" that would be built by the memoized recursive function.) A map called `processed` tracks the status of items, marking whether they have been partially or fully processed. The first time we see an item in `unprocessed`, we mark it as :seen-once (in the `processed` map), but keep it in `unprocessed`, adding all its dependencies to `unprocessed` as well. The second time we see the item in `unprocessed`, we can conclude that all its dependencies have already been fully processed, and therefore can mark this item as :done and move it to the final `stack`. Now it works: => (all-dependencies 30) [3 2 7 0 5 10 15 1 6 12 20 25 30] The important thing to note here is that all-dependencies is a general strategy (known as topological sorting), and you can just pick an implementation and use it for any sort of memoization/priming task. All you need to do is code the `dependencies` function in a way that mirrors your recursive dependencies, and plug it into this or another similar implementation of topological sort. -- -- 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.