在Haskell中汇总1到1,000,000会导致堆栈溢出.引擎盖下发生了什么？

Question

我有以下代码.

main = print $ sum [1..1000000]

当我运行时,我得到一个堆栈溢出:

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

我习惯于像Python那样的命令式语言,这些算法似乎没有问题:

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

Haskell显然是不同的,但我不太明白是什么导致堆栈溢出？在引擎盖下发生什么导致Haskell中的堆栈溢出？

Answer 1

整个问题仅与GHC <7.10有关.在最近的版本中,sum [1..1000000]在恒定空间中工作得很好,至少在内置数字类型上.

sum 是^_曾经用邪恶的foldl¹ ^_来实现,这不像它应该的那样严格.因此,你得到sum的本质上是一堆thunk,和你的输入一样大.我认为有一个讨论为什么它在某种程度上这样做... IMO它基本上只是愚蠢的,因为总和通常不能懒得消耗,因为使用严格的折叠是显而易见的.

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

¹实际上,foldl仅在报告版本中使用...但带累加器的显式递归版本当然不会更好.

有没有理由他们没有解决这个问题？ (2认同)
所以如果我没记错的话,人们还没有打扰的唯一原因就是当你用`-O2`编译时问题就会消失(但是,我仍然认为它应该被修复).此外,jozefg是正确的,'foldl` /`foldl'`都是流融合的坏消费者.正确的版本是`Data.Foldable.foldl',应该是正式版本. (2认同)
我怀疑它没有被改变的原因是Haskell报告指定了懒惰的行为. (2认同)