Отбрасывает ли Haskell промежуточные результаты во время ленивой оценки?

Если я определяю последовательность Фибоначчи рекурсивно:

fibo_lazy_list = 0 : 1 : zipWith (+) fibo_lazy_list (tail fibo_lazy_list)

Затем запросите первый элемент выше заданного значения, скажем:

print $ find (>100) fibo_lazy_list

Я понимаю, что Haskell оценивает только те элементы, которые необходимы для получения печатных результатов. Но все ли они сохраняются в памяти до печати? Поскольку для вычисления последнего требуются только два элемента списка, освобождает ли Haskell крайние левые элементы или список продолжает расти в памяти?


lazy-evaluation haskell lazy-sequences
person vkubicki    schedule 02.02.2021    source источник
comment
Связано: stackoverflow. ком/вопросы/40562489/   -  person danidiaz    schedule 03.02.2021

Ответы (1)


arrow_upward
10
arrow_downward

Это зависит.

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

В вашем примере ведущие элементы fibo_lazy_list (кстати, используйте camelCase, а не underscore_case в Haskell) не будут удаляться сборщиком мусора, пока на fibo_lazy_list ссылается что-то, что все еще может быть оценено. Но как только это выходит за рамки, это невозможно. Так что, если вы напишете это так

print $ let fibo_lazy_list = 0 : 1 : zipWith (+) fibo_lazy_list (tail fibo_lazy_list)
        in find (>100) fibo_lazy_list

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

Однако, если fibo_lazy_list определен на верхнем уровне и является CAF (как это будет, если тип не полиморфен)

fiboLazyList :: [Integer]
fiboLazyList = 0 : 1 : zipWith (+) fiboLazyList (tail fiboLazyList)

main :: IO ()
main = do
   ...
   print $ find (>100) fiboLazyList
   ...

тогда вам лучше ожидать, что все ведущие элементы останутся в памяти даже после извлечения >100.

Здесь может помочь оптимизация компилятора, а также аннотации строгости. Но, как я уже сказал, это немного больно в Haskell.

person leftaroundabout    schedule 02.02.2021