Haskell: повторите функцию много раз без stackoverflow

Как новичок в 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 для многократного итерации функции?

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

Ответ 1

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

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 без проблем.