haskell - 如何避免堆栈空间溢出？

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

These links here会给你一个很好的介绍你的问题太多重击 (空间泄漏)。

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

{-# 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