[Haskell-cafe] Stack vs Heap allocation

[Chaddaï Fouché]

2008/5/10 Edsko de Vries <devriese at cs.tcd.ie>:
>> The key reason why nested additions take stack space, is because (+) on
>> Integers is *strict* in both arguments.  If it were somehow non-strict
>> instead, then the unevaluated parts of the number would be heap-allocated
>> rather than stack-allocated.
>
> I don't understand. Could you elaborate?
>

The key problem here is not that a huge thunk is built : it is
allocated on the heap.
But when it is forced, the fact that (+) is strict means that all the
calls of (+) that had been created must go on the stack...

So in the example of "fold (+) 0 [long list]", the problem is not in
the evaluation of foldl which only build a big thunk (with a tail
recursion), the problem intervene when you must evaluate the big thunk
since then you need to stack all the (+)... If (+) was lazy it
wouldn't be a problem since you would only need to call one (+) to get
a value (which will go in the heap).

-- 
Jedaï