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

Hi Bas, I'd like to share some thoughts with you. Let's say I'm unable, for whatever reason, to force full evaluation of the accumulator during a foldl. So I have this huge build up of thunks, which causes a stack overflow when the thunks are being reduced. I wonder if I could write some sort of "chunked fold" which basically still produces the same amount of thunks but in a way so that the do not go on the stack all at once for reduction and thus do not cause a stack overflow. Kind of a tree. I'd sincerely appreciate your thoughts on this. Günther Bas van Dijk schrieb:

On Fri, Mar 20, 2009 at 2:01 PM, GüŸnther Schmidt 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 the:

((((((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!

regards,

Bas