Puzzler, thanks for all your excellent ideas!
I get the impression that you're as troubled as I am by the brokenness of
recursion, but it looks like it can be worked around.
A bit of memory thrown at the JVM stack combined with a better memoization
technique should work in most of the cases that trampoline and recur miss.
It's obviously not ideal that the stack and heap can't coexist under one
limit, but worst case that means that you need twice as much memory as you
should. I can live with that.
John.
On Monday, September 23, 2013 8:59:19 AM UTC+1, puzzler wrote:
>
> 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.
