如何避免堆栈空间溢出？

Question

如果我需要获取包含内存密集型元素的大列表的值，我对 GHC 抛出堆栈溢出感到有点惊讶。 我确实预计 GHC 有 TCO，所以我永远不会遇到这种情况。

为了最大程度地简化情况，请查看以下返回斐波那契数的函数的简单实现（取自 HaskellWiki）。目标是显示第一百万个数字。

import Data.List

# elegant recursive definition
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

# a bit tricky using unfoldr from Data.List
fibs' = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)

# version using iterate
fibs'' = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

# calculate number by definition
fib_at 0 = 0
fib_at 1 = 1
fib_at n = fib_at (n-1) + fib_at (n-2)

main = do
    {-- All following expressions abort with
        Stack space overflow: current size 8388608 bytes.
        Use `+RTS -Ksize -RTS' to increase it.
     --}
    print $ fibs !! (10^6)
    print . last $ take (10^6) fibs
    print $ fibs' !! (10^6)
    print $ fibs'' !! (10^6)

    -- following expression does not finish after several 
    -- minutes
    print $ fib_at (10^6)

源代码是使用 ghc -O2 编译的。

我做错了什么？我想避免使用增加的堆栈大小或其他特定编译器选项进行重新编译。

Answer 1

这些 链接 这里将很好地介绍您的thunk太多（空间泄漏）问题。

如果您知道要注意什么（并且有一个不错的惰性求值模型），那么解决它们就很容易了，例如：

{-# LANGUAGE BangPatterns #-}                        

import Data.List                                     

fibs' = unfoldr (\(!a,!b) -> Just (a,(b,a+b))) (0,1) 

main = do                                            
    print $ fibs' !! (10^6)  -- no more stack overflow                   

Answer 2

所有的定义（除了无用的 fib_at ）都会延迟所有 + 操作，这意味着当您选择了第 100 万个元素时，它是一个带有 100 万个延迟添加的 thunk。你应该尝试一些更严格的东西。

Answer 3

正如其他人指出的那样，Haskell 很懒，您必须强制对 thunk 求值以避免堆栈溢出。
在我看来，这个版本的 fibs' 应该工作到 10^6：

fibs' = unfoldr (\(a,b) -> Just (seq a (a, (b, a + b) )))  (0,1)

我建议研究这个 Folds 的 wiki 页面 并查看 seq 函数。