Summing 1 through 1,000,000 in Haskell gives a stack overflow. What's happening under the hood?

Question

I have the following code.

main = print $ sum [1..1000000]

When I run I get a stack overflow:

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

I'm accustom to imperative languages like Python which seem to have no problem with such a calculation:

sum(range(100000000))  # I'm not even using a generator.
4999999950000000

Haskell is obviously different, but I don't quite understand what's happening to cause the stack overflow? What's going on under the hood to cause the stack overflow in Haskell?

Answer 1

This entire question is only relevant for GHC<7.10. In recent versions, sum [1..1000000] works just fine in constant space, at least on built-in number types.

---

sum is^{_{used to be}} implemented with the evil foldl¹, which isn't as strict as it should be. Thus, what you get from sum is essentially a pile of thunks, as large as your input. I think there was a discussion about why it is done this way here at some point... IMO it's basically just stupid, since sums can't normally be consumed lazily anyway it's just obvious to use a strict fold.

Prelude> :m +Data.List
Prelude Data.List> foldl' (+) 0 [1..1000000]
500000500000

---

¹Actually, foldl is only used in the report version... but the explicit-recursion version with accumulator is of course no better.

Answer 2

sum is defined in terms of foldl which is lazy in a left associative sort of way so that it has to generate thunks for the whole list before evaluating a single (in this case addition) expression.

You could also define sum in terms of foldls stricter counterpart foldl' like so:

sum' = foldl' (+) 0

See Foldr. Foldl. Foldl'. from the Haskell Wiki for a good explanation of how foldl has to generate thunks for every calculation without being able to evaluate anything, which will cause a Stack Overflow.