[Haskell-cafe] Stacking State on State.....
wren ng thornton
wren at freegeek.org
Mon Mar 2 00:49:49 EST 2009
> Again I understand that foldl' is the strict version of foldl, and as we are
> summing elements we can use either foldl or foldr. I'm assuming this is
> another thunk optimisation. Does foldl not actually calculate the sum, but
> moreover it creates an expression of the form a+b+c+d+e+.... Where foldl'
> will actually evaluate the expression to an atomic number?
It's two things.
The first thing is that foldl/foldl' is tail-recursive which can be
optimized into a loop in the assembly, and ensures that the fold won't
stack overflow (though that says nothing about what the fold builds).
The second is that foldl' is strict. That is, rather than building up a
large thunk at all, at each step of the recursion we force the
accumulator. This is essential to prevent stack overflows when
evaluating the accumulator for atomic types like Int or Double. The same
number of evaluations happen, but they're ordered differently so they
can be amortized across the recursion, rather than being demanded all at
once (which can exceed the resources of our non-infinite computers). For
non-atomic types the added strictness is less essential.
The pyramid shape of http://www.beadling.co.uk/mc2_3stacks.pdf is a
canonical image of not letting go of memory incrementally, which is
often the result of being too lazy. You see the same shape with, say,
building up a very long list, but holding onto the first element (which
prevents the GC from cleaning up behind you as you traverse the list).
Which is the same as building up a very large computation, but holding
off on evaluating it.
The image of http://www.beadling.co.uk/mc2_2stacks.pdf looks jittery,
but if we zoomed out a bit we'd see that it's a flat line, which means
we're freeing memory as quickly as we're allocating it, rather than
building up anything large in memory. Ideally, all programs should look
More information about the Haskell-Cafe