是什么导致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

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

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.但是通常没有防止堆栈溢出的灵丹妙药,你只需要了解程序的评估行为.这有时很难.

但是,如果我理解正确的话,堆栈溢出总是来自于试图评估一个巨大的thunk.因此,寻找可以创建它们的地方,并强制评估更早发生.