Haskell是否发生堆栈溢出错误？

Question

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

Answer 1

堆栈溢出不会像在 Java 中那样在 Haskell 中发生，因为计算和函数调用的发生方式不同。

在Java和C等类似语言中，函数调用是使用调用栈实现的。当你调用一个函数时，函数的所有局部变量都被分配到一个调用栈上，当函数结束时，函数被弹出栈。嵌套调用太多，调用栈会溢出

在 Haskell 中，函数调用不一定是这样工作的。在大多数编译器中，例如 GHC，Haskell 函数调用是 而不是 使用调用堆栈实现的。它们是使用完全不同的过程实现的，使用堆上的 thunk 分配。

因此，大多数 haskell 实现不会首先为函数调用实现调用堆栈，因此堆栈溢出的想法是没有意义的。这就像在只有淋浴的更衣室里谈论浴缸溢出一样。

(GHC 确实使用调用堆栈进行 thunk 评估，但不用于函数调用。因此可能发生的堆栈溢出与来自 Java、C 等的堆栈溢出具有完全不同且无关的性质。 )

Answer 2

由于懒惰，

Haskell 使用堆栈的方式与 Java 不同。

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

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

所以如果 f 是一个递归函数，每次调用 f 都会生成一个 thunk，并且 case 在这个结果上生成一个堆栈帧，但是这些帧是只有嵌套时thunk 之间存在依赖关系。事实上，这就是 seq 原语所做的：a `seq` b 意思是“在 b、returning b 之前计算 a”，但是你也可以认为是在a上增加了b的依赖，所以当b被求值的时候，a也被强制

当你有很深的 thunks 链来计算时，你可能会得到堆栈溢出，例如在过于懒惰的 foldl 函数中：

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

这会生成一个 thunk 链，如下所示：

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

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

Haskell是否发生堆栈溢出错误？

Do stack overflow errors occur in Haskell?

stack-overflow

recursion

haskell