nth yields "java.lang.OutOfMemoryError: Java heap space"
arasoft
this:
(defn fib-seq []
((fn more [a b]
(lazy-seq (cons a (more b (+ a b)))))
0 1)
)
(nth (fib-seq) 200000)
However, this works fine:
(defn xth [coll i]
(if (zero? i) (first coll) (recur (rest coll) (dec i))))
(xth (fib-seq) 200000)
Am I doing anything wrong, or is this a bug?
Daniel Lyons
You aren't doing anything wrong, it's just that recur is a local jump
which creates no stack and calling a function recursively is not. In
other words Clojure doesn't have built-in tail call elimination, but
recur creates the same effect. (I actually prefer this behavior
because it's easy to see where you're paying the penalty for recursion
and where you aren't, unlike in OCaml, Scheme and Haskell, where it
can be easy to get confused about which form is the final position.)
—
Daniel Lyons
Lennart Staflin
overflow. It is not a recursion problem. I think it is that nth hangs
on to the head of the lazy fib sequence, and therefor all the elements
including the big integers can not be garbage collected.
The xth function does not hang on to the head, and all the
intermediate elements can be garbage collected.
//Lennart Staflin
Meikel Brandmeyer
Am 04.07.2009 um 17:11 schrieb Lennart Staflin:
> I don't think this explains it. It is a OutOfMemoryError not a stack
> overflow. It is not a recursion problem. I think it is that nth hangs
> on to the head of the lazy fib sequence, and therefor all the elements
> including the big integers can not be garbage collected.
>
> The xth function does not hang on to the head, and all the
> intermediate elements can be garbage collected.
This was my first thought, too. But this is not
the case. If the collection "is" Sequential, the
seq is obtained from it via seq() and then the
original pointer is nulled. Maybe this gets
optimised away by the JVM?
Sincerely
Meikel
Rich Hickey
RT.nth, now removed. Thanks for the report!
http://github.com/richhickey/clojure/commits/master
Rich