haskell - Haskell 中是否会发生堆栈溢出错误？

Question

作为一种纯函数式编程语言，Haskell 大量使用递归。 Haskell 中是否会出现堆栈溢出错误，就像在 Java 中一样？为什么或者为什么不？

Answer 1

由于惰性，Haskell 使用堆栈与 Java 不同。

在 Java 中，调用方法时会创建堆栈帧，并在方法返回时释放堆栈帧。所以如果 f()是递归方法，每次递归调用f()生成一个栈帧，这些帧是严格嵌套的。当你有很深的递归调用链时，可能会出现堆栈溢出，例如 f() -> f() -> f() -> … .

而在 Haskell 中，调用函数时会创建一个 thunk。当使用模式匹配(例如 case )强制 thunk 时创建堆栈帧，并在 thunk 的评估完成到足以返回一个值(可能包含更多未评估的 thunk)时释放。

所以如果 f是递归函数，每次调用f生成一个 thunk，并且 case结果会生成一个堆栈帧，但这些帧仅在 thunk 之间存在依赖关系时才会嵌套。事实上，这就是 seq原语:a `seq` b意思是“评估a之前 b , 返回 b ”，但也可以认为是添加了b的依赖在 a , 所以当 b被评估，a也是被迫的。

当你有一个很深的 thunk 链要评估时，你可能会发生堆栈溢出，例如在过度懒惰的 foldl 中。功能:

foldl (+) 0 [1..5]
==
foldl (+) 0 (1 : 2 : 3 : 4 : 5 : [])
==
((((0 + 1) + 2) + 3) + 4) + 5

这会生成一连串的 thunk，如下所示:

((+)
    ((+)
        ((+)
            ((+)
                ((+)
                    0
                    1)
                2)
            3)
        4)
    5)

当我们强制结果时(例如，通过打印它)，我们需要沿着这条链一路下降，以便能够开始评估它，在 (+) 0 1砰。

所以 foldl通常会为大输入产生堆栈溢出，这就是为什么大多数时候应该使用 foldl' (这是严格的)当你想要一个左关联折叠时。 foldl' 不是构建嵌套的 thunk 链，而是立即评估中间结果( 0+1 = 1， 1+2 = 3， 3+3 = 6，...)。