gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 22:16:55 24 4
gpt4 key购买 nike

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

最佳答案

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

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。所以寻找可以创建这些的地方,并强制评估更早发生。

关于haskell - 通常是什么导致haskell中的 "Error C stack overflow",我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2462780/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com