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 <[email protected]> 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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
