Summing 1 through 1,000,000 in Haskell gives a stack overflow. What's happening under the hood?
haskell, stack-overflow, sum
Solution
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` isused to be implemented with the evil `foldl`1, 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
1Actually, `foldl` is only used in the report version... but the explicit-recursion version with accumulator is of course no better.
Problem
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?