[Haskell-cafe] Stacking State on State.....

[wren ng thornton]

Phil wrote:
> 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 
like this.

-- 
Live well,
~wren