haskell - 在 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 is^{_{used to be}} implemented with the evil foldl ¹ ，这并不像应有的那样严格。因此，您从 sum 获得的信息本质上是一堆 thunk，与您的输入一样大。我认为有人讨论过为什么在某些时候会以这种方式完成... IMO 它基本上只是愚蠢的，因为无论如何通常不能懒惰地消耗总和，所以使用 strict fold 很明显.

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

1其实， foldl仅在报告版本中使用...但是带有累加器的显式递归版本当然也好不到哪里去。