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