[Haskell-cafe] Stupid newbie question
Brian Hurt
bhurt at spnz.org
Fri Jan 5 21:40:33 EST 2007
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
More information about the Haskell-Cafe
mailing list