Haskell: повторять функцию большое количество раз без переполнения стека - PullRequest
Новая
       6

Haskell: повторять функцию большое количество раз без переполнения стека

11 голосов
/ 18 января 2012

Как новичок в Haskell, я пытаюсь выполнить итерацию функции (например, логистической карты) большое количество раз. В императивном языке это будет простой цикл, однако в Haskell я получаю переполнение стека. Возьмите для примера этот код: 

main  = print $ iter 1000000

f x = 4.0*x*(1.0-x)

iter :: Int -> Double
iter 0 = 0.3
iter n = f $ iter (n-1)

Для небольшого числа итераций код работает, но для миллиона итераций я получаю переполнение стека: 

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

Я не могу понять, почему это происходит. Хвостовая рекурсия здесь должна быть в порядке. Может быть, проблема в ленивой оценке. Я экспериментировал с несколькими способами принудительной строгой оценки, вставляя $! или seq в различные позиции, но безуспешно.

Каким был бы способ Haskell итерировать функцию огромное количество раз?

Я попробовал предложения из связанных постов: здесь или здесь , но я всегда заканчивал стеком потока для большого количества итераций, например main = print $ iterate f 0.3 !! 1000000.

1 Ответ

24 голосов
/ 18 января 2012

Проблема в том, что ваше определение 

iter :: Int -> Double
iter 0 = 0.3
iter n = f $ iter (n-1)

пытается оценить в неправильном направлении. Развернув его за несколько шагов, мы получим 

iter n = f (iter (n-1))
       = f (f (iter (n-2)))
       = f (f (f (iter (n-3))))
       ...

и весь стек вызовов от iter 1000000 до iter 0 должен быть построен, прежде чем что-либо можно будет оценить. Это было бы то же самое на строгом языке. Вы должны организовать это так, чтобы часть оценки могла проходить до повторения. Обычный способ - иметь параметр накопления, например 

iter n = go n 0.3
  where
    go 0 x = x
    go k x = go (k-1) (f x)

Затем добавление аннотаций строгости - в случае, если компилятор их еще не добавил - заставит работать бесперебойно без использования стека.

Вариант iterate имеет ту же проблему, что и ваш iter, только стек вызовов построен изнутри, а не снаружи, как у вас. Но поскольку iterate строит свой стек вызовов наизнанку, более строгая версия iterate (или модель потребления, где более ранние итерации выполняются раньше) решает проблему, 

iterate' :: (a -> a) -> a -> [a]
iterate' f x = x `seq` (x : iterate' f (f x))

вычисляет iterate' f 0.3 !! 1000000 без проблем.

...