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.
