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

G?uenther Schmidt redcom at fedoms.com
Sat Mar 21 10:34:22 EDT 2009

```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 <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
> 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

```