2008/5/10 Edsko de Vries
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ï