[Haskell-cafe] Stupid newbie question

[Brian Hurt]

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