haskell - 通常在haskell中导致“错误C堆栈溢出”的原因

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，因为它总是会产生巨大的冲击。请改用 foldl'。如果输出类型具有惰性结构（例如列表或函数），请使用 foldr。但是一般来说没有避免堆栈溢出的灵丹妙药，您只需要了解程序的评估行为即可。有时这可能很难。

但是，如果我理解正确，堆栈溢出总是来自试图评估一个巨大的 thunk。因此，寻找可以创建这些的地方，并强制评估提前进行。

Answer 2

失控的递归是最有可能的候选者......您需要提供更多信息才能获得更准确的答案。

Answer 3

下面是一些可能导致递归失控的代码：

main =
  let x = x :: Int
  in print x

这里发生的情况是，当x被评估时print x它开始，然后发现要完成它需要评估的评估x。

Answer 4

最可能的原因必须是不受控制的递归。每个递归调用为其输入/输出参数消耗更多的堆栈空间。