[Haskell-cafe] Re: A guess on stack-overflows - thunks build-up and tail recursion

Bas van Dijk v.dijk.bas at gmail.com
Fri Mar 20 09:42:12 EDT 2009

On Fri, Mar 20, 2009 at 2:01 PM, GüŸnther Schmidt <gue.schmidt at web.de> wrote:
> The problem occurs when the result value is needed and thus the thunks need
> to be reduced, starting with the outermost, which can't be reduced without
> reducing the next one .... etc and it's these reduction steps that are
> pushed on the stack until its size cause a stack-overflow.

Oh yes of course! Indeed a foldl:

foldl f z []     = z
foldl f z (x:xs) = foldl f (z `f` x) xs

Is compiled to:

foldl f z xs = case xs of
                 []     -> z
                 (x:xs) -> let z' = f z x
                           in foldl f z' x

So the z' is allocated on the heap.

So it turns out that in my " Foldr Foldl Foldl' " article the stack
overflow message is listed to soon. It should actually be lised after

((((((0 + 1) + 2) + 3) + 4) + ...) + 999999) + 1000000

I will fix it when I get home from work and nobody has beat me to it.

Thanks for pointing this out!



More information about the Haskell-Cafe mailing list