haskell - 通常是什么导致haskell中的 "Error C stack overflow"

Question

Hugs Haskell 实现中“错误 C 堆栈溢出”的常见原因是什么。

Answer 1

如果您习惯了通常进行尾递归分解的函数式语言，就会出现这种情况。假设你有一个函数:

sum = go 0
    where
    go accum [] = accum
    go accum (x:xs) = go (accum+x) xs

顺便说一下，这与

sum = foldl (+) 0

如果我们评估函数，我们可以看到问题:

sum [1,2,3,4]
go 0 [1,2,3,4]
go (0+1) [2,3,4]
go ((0+1)+2) [3,4]
go (((0+1)+2)+3) [4]
go ((((0+1)+2)+3)+4) []
(((0+1)+2)+3)+4

现在要评估该表达式 Haskell 使用堆栈:

EXPR            | STACK
(((0+1)+2)+3)+4 | 
((0+1)+2)+3     | +4
(0+1)+2         | +3 +4
(0+1)           | +2 +3 +4
1               | +2 +3 +4
3               | +3 +4
6               | +4
10              |

这就是可能发生溢出的地方。如果您计算 sum [1..10^6]，那么该堆栈将有一百万个条目深。

但请注意这里的病理。您递归遍历列表只是为了构建一个巨大的 fscking 表达式(“thunk”)，然后使用堆栈来评估它。我们宁愿在递归时评估它，通过使尾递归严格:

sum = go 0
    where
    go accum [] = accum
    go accum (x:xs) = accum `seq` go (accum+x) xs

这表示在尝试评估递归调用之前评估 accum ，所以我们得到(这可能需要一些耐心才能理解):

sum [1,2,3,4]
go 0 [1,2,3,4]
let accum = 0 in accum `seq` go (accum+1) [2,3,4]
go (0+1) [2,3,4]
let accum = 0+1 in accum `seq` go (accum+2) [3,4]
go (1+2) [3,4]
let accum = 1+2 in accum `seq` go (accum+3) [4]
go (3+3) [4]
let accum = 3+3 in accum `seq` go (accum+4) []
go (6+4) []
6+4
10

因此，当我们遍历列表时，我们正在计算总和，因此我们不必使用深堆栈来评估结果。这个修改后的尾递归模式被封装在 Data.List.foldl' 中，所以:

sum = foldl' (+) 0

一个好的经验法则是永远不要使用 foldl，因为它总是会产生巨大的 thunk。使用 foldl' 代替。如果输出类型具有惰性结构(例如列表或函数)，请使用 foldr。但是通常没有避免堆栈溢出的 Elixir ，您只需要了解程序的评估行为即可。这有时可能很难。

但是，如果我理解正确的话，堆栈溢出总是来自尝试评估一个巨大的 thunk。所以寻找可以创建这些的地方，并强制评估更早发生。