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