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

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

Эти ссылки здесь дадут вам хорошее представление о вашей проблеме слишком много громад (космические утечки).

Если вы знаете, на что обращать внимание (и имеете достойную модель ленивых вычислений), то решить их довольно просто, например:

{-# 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) будут задерживать все операции +, что означает, что когда вы выбрали миллионный элемент, это будет thunk с миллионом отложенных дополнений.Вы должны попробовать что-то более строгое.

Answer 3

Как уже отмечали другие, из-за того, что Haskell ленив, вы должны форсировать оценку thunks, чтобы избежать переполнения стека.Мне кажется, что эта версия выдумок должна работать до 10 ^ 6:

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

Я рекомендую изучить эту вики-страницу на Folds и взглянуть на Функция seq.