Iterate выдает ошибки StackOverflow

Вы, вероятно, не «неправильно понимаете всю ленивую оценку», но в этом случае вы дважды укушены слишком ленивой оценкой.

И хотя в этом отношении ГХК работает точно так же, как и Фреге, результат получается другим и, по-видимому, неблагоприятным для Фреге.

Но причина того, что Haskell может работать с действительно большими переходами [см. ниже], в то время как Frege преждевременно завершает работу с переполнением стека, заключается в том, как системы времени выполнения управляют кучей и стеком. Haskell RTS является гибким и может выделить для стека огромные части доступной памяти, если возникнет такая необходимость. В то время как исполняющая система Фреге представляет собой JVM, которая обычно начинается с крошечного стека, достаточного для обработки глубины вызовов в несколько сотен. Как вы заметили, предоставление JVM достаточного стекового пространства заставляет думать так же, как и в GHC.

Из-за нехватки места в стеке в JVM мы разработали некоторые методы во Фреге, чтобы избежать нежелательной и ненужной лени. Два из них будут описаны ниже. В конце концов, во Фреге вы вынуждены заранее контролировать негативные последствия лени, в то время как разработчик GHC может с радостью писать код, не обращая на это внимания.

Чтобы понять следующее, нам необходимо ввести понятие «thunk». Преобразователь - это, прежде всего, выражение, которое еще предстоит оценить. Например, поскольку кортежи ленивы, такое выражение, как

(b, b+a)

компилируется в приложение конструктора кортежей от (,) до b и {a+b}, где обозначение { e } для целей этого обсуждения означает некоторое зависимое от реализации представление thunk, которое обещает вычислить выражение e при оценке. Кроме того, преобразователь запоминает свой результат при оценке, поэтому всякий раз, когда тот же преобразователь оценивается снова, он просто возвращает предварительно вычисленный результат. (Конечно, это возможно только в чистом функциональном языке.)

Например, во Фреге для представления санков есть класс Delayed<X>, реализующий Callable<X> и обеспечивающий запоминание результата.

Теперь мы будем исследовать, каков результат

next_fib (next_fib (0, 1)) 

является. Внутреннее приложение приводит к:

(1, {0+1})

а затем внешний вычисляет из этого:

({0+1}, {1+{0+1}})

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

Теперь рассмотрим, что происходит, когда вычисляется преобразователь для 4000-го числа выдумки, что происходит, например, когда вы печатаете его. Он должен будет выполнить сложение, но добавляемые числа на самом деле являются преобразовательами, которые должны быть оценены, прежде чем сложение может иметь место. Таким образом, каждый вложенный преобразователь означает вызов метода оценки этого переходника, если только преобразователь уже не оценен. Следовательно, чтобы напечатать 4000-е число, нам нужна глубина стека не менее 4000 в случае, когда никакой другой преобразователь этой серии ранее не вычислялся.

Итак, первой мерой была замена ленивого конструктора кортежей на строгий:

(b; a+b)

Он не создает преобразователи, а сразу вычисляет аргументы. Это недоступно в Haskell, чтобы сделать то же самое, вам нужно сказать что-то вроде:

let c = a+b in b `seq` c `seq` (b,c)

Но это был не конец истории. Оказалось, что вычисление fib 4000 по-прежнему переполняло стек.

Причина в реализации iterate, которая выглядит следующим образом:

iterate f x = x : iterate f (f x)

Это создает бесконечный список

[ x, f x, f (f x), f (f (f x)), ...]

Излишне говорить, что все термины, кроме первого, являются переходниками!

Обычно это не проблема, когда элементы списка оцениваются в последовательном порядке, потому что когда, например, 3-й член

{f {f x}}

оценивается, внутренний преобразователь выполнен уже вычислен и сразу же возвращает результат. В общем, нам нужна только достаточная глубина стека, чтобы достичь первого ранее вычисленного члена. Вот демонстрация прямо из онлайн-REPL frege на try.frege-lang.org.

frege> next (a,b) = (b; a+b) :: (Integer, Integer)
function next :: (Integer,Integer) -> (Integer,Integer)
frege> fibs = map fst $ iterate next (0,1)
function fibs :: [Integer]
frege> fib = (fibs!!)
function fib :: Int -> Integer
frege> map (length . show . fib) [0,500 ..]
[1,105,209,314,418,523,627,732,836,941,1045,1150,...]
frege> fib 4000
39909473435004422792081248094960912600792...

Здесь с помощью карты мы принудительно вычисляем каждое 500-е число (поскольку REPL требует вывода, он будет печатать только начальные части бесконечных списков) и вычисляем длину десятичного представления каждого числа (просто чтобы не отображать большие полученные числа). Это, в свою очередь, вызывает оценку 500 предыдущих чисел, но это нормально, так как для этого достаточно места в стеке. Как только это будет сделано, мы сможем вычислить даже fib 4000! Потому что теперь все преобразователи до 6000 уже оценены.

Но мы можем сделать еще лучше с немного улучшенной версией iterate, которая использует строгий конструктор головы (!:):

a !: as = a `seq` (a:as)

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

С этими двумя изменениями мы получаем программу, требования к стеку которой больше не зависят от аргумента fib. Вот доказательство:

frege> iterate' f x = x !: iterate' f (f x)
function iterate' :: (a->a) -> a -> [a]
frege> fibs2 = map fst $ iterate' next (0,1)
function fibs2 :: [Integer]
frege> (length . show . (fibs2 !!)) 4000
836
frege> (length . show . (fibs2 !!)) 8000
1672
frege> (length . show . (fibs2 !!)) 16000
3344
frege> (length . show . (fibs2 !!)) 32000
6688
frege> (length . show . (fibs2 !!)) 64000
13375
frege> (length . show . (fibs2 !!)) 128000
java.lang.OutOfMemoryError: Java heap space

Что ж, теперь нам потребуется больше пространства в куче, чтобы хранить более 100 000 огромных чисел. Но обратите внимание, что больше не было проблемы со стеком для вычисления 32 000 новых чисел на последнем шаге.

Мы могли бы избавиться от проблемы пространства в куче с помощью простого рекурсивного определения хвоста, которому не нужно отмечать все эти числа:

fib :: Int -> Integer
fib n = go n 0 1 where
    go :: Int -> Integer -> Integer -> Integer
    go 0 !a !b = a
    go n !a !b = go (n-1) b (a+b)

Я думаю, это будет даже быстрее, чем обход списка.

В отличие от (?) в Clojure, прямой доступ к списку — O(n), а длинные списки занимают много места. Поэтому, если вам нужно что-то кешировать и иметь верхний предел, вам лучше использовать массивы. Вот 2 способа построить массив из 10000 фибов:

frege> zzz = arrayFromList $ take 10000 $ map fst $ iterate (\(a,b) -> (b; a+b)) (0n,1)
function zzz :: JArray Integer
frege> elemAt zzz 4000
39909473435004422792081248094960912600792570982820257 ...

Это работает, потому что промежуточный список никогда не должен существовать как единое целое. И после создания доступ O (1)

А еще есть специальная функция для создания таких кешей:

yyy = arrayCache f 10000 where 
       f 0 a = 0n
       f 1 a = 1n
       f n a = elemAt a (n-1) + elemAt a (n-2)
fib = elemAt yyy

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

Таким образом, вы сохраните свою добрую привычку предпочитать комбинаторы явной рекурсии. Пожалуйста, попробуйте.