Как избежать стека зр ace переполняется?

Я был немного удивлен тем, что 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 .

Что я делаю не так? Я бы хотел избежать перекомпиляции с увеличенным размером стека или другими специфическими параметрами компилятора.

5
задан Raeez 23 June 2011 в 20:41
поделиться