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?
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.
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 foldl
s 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With