On Fri, 5 Jan 2007, Jeremy Shaw wrote:
Hi,
In this case, the stack overflow you are seeing is due to laziness not
tail recursion.
Aha. I knew it was something stupid.
Because you never demand the value of any element in the list, Haskell
never bothers to calculate it. So you have a list that looks like:
[ i, i - 1, (i - 1) - 1, ((i - 1) - 1 - 1), .. ]
So, by the time you get up to some big numbers, you have built up a
very large thunk. For some reason this is causing a stack overflow.
Actually, this makes sense to me. Recursively forcing lazy thunks is not
tail recursive, it needs to allocate stack frames. So if a million-deep
recursive thunk, forcing it is a problem.
The easiest solution is to make things a little more strict. For
example, if you change:
nth i (x:xs) = if i < 0 then Empty else nth (i-1) xs
to:
nth i (x:xs) = x `seq` (if i < 0 then Empty else nth (i-1) xs)
This will force x enough that things do not overflow.
j.
ps. just a warning, seq is not entirely straightforward to use, so
while it works in this case, it may not always work for you. I think
there might be a wiki page somewhere that explains how to avoid space
leaks in greater detail, but I can't seem to find it.
Another solution that does not involve using seq would be to replace
the above line with these two lines:
nth i (0:xs) = if i < 0 then Empty else nth (i-1) xs
This looks to be a typo, not sure if it's mine or yours. The definition I
was playing with was (or should be):
nth i (x:xs) = if i < 0 then Empty else nth (i-1) xs
Brian
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
