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)

当我们强制执行结果时(例如,通过打印它),我们需要一直向下移动此链,以便能够在thunk 处开始评估它(+) 0 1.

因此,foldl经常会为大输入产生堆栈溢出,这就是为什么foldl'在需要左关联折叠时大多数时候应该使用(严格).而不是构建嵌套的thunk的链的,foldl'计算紧接在中间结果(0+1 = 1,1+2 = 3,3+3 = 6,...).