Код

fibs = 0 : 1 : zipWith $+$ fibs $tailfibs$

— это классическое ленивое определение бесконечного списка чисел Фибоначчи. Что тут происходит:

fibs — список, первый элемент 0, второй 1.zipWith $+$ fibs $tailfibs$ складывает список с его хвостом поэлементно, поэтому получается последовательность сумм предыдущих двух элементов. Благодаря ленивости список самопорождает: новые элементы вычисляются по мере запроса.

Что даёт ленивость $плюсы$

Можно оставить бесконечную структуру и брать сколько нужно $streaming$: fibs !! 10 вычислит только первые 11 элементов.Шэринг: если несколько мест кода читают один и тот же fibs, ранее вычисленные элементы сохраняются и повторно не пересчитываются — экономия времени.Композиция: удобно конструировать конвейеры вычислений без явного управления памятью.

Где ленивость мешает $минусы/подводныекамни$

Удержание префикса списка $spaceleak$. Если у вас сохраняется ссылка на голову fibs $например,fibs—top-levelCAF$, то все уже построенные элементы остаются в памяти. При обращении к n-му элементу $fib!!n$ будет построена и сохранена вся префиксная часть длины ≈ n — O$n$ ячеек памяти.Накопление отложенных вычислений $thunks$. Если при наращивании списка значения не принудительно не сворачиваются в нормальное представление, можно накопить большую цепочку thunk'ов и получить рост памяти / стековые проблемы.Размер самих чисел. Для типа Integer числа растут экспоненциально по длине в битах, так что и память на отдельный элемент может быть большой — это отдельный фактор.

Сколько памяти требуется для доступа к n-му элементу

В типичном случае при использовании вышеописного top-level fibs и взятии элемента fibs !! n вы аллоцируете примерно n конс-узлов $каждыйузелсодержитссылкуназначениеиссылкунаследующийузел$ плюс сами значения $Integer/Int$. Итого память ~ O$n$ $спайнсписка+значения$. Для Integer добавляется память на bigint $растётсn$.Если вы не сохраняете ссылку на голову списка и генерация списка используется только для одного последовательного прохода, GC может освободить уже пройденные узлы; тогда максимальная занимаемая память может быть O$1$ $потомучтостарыеузлыуженезадействованы$. Но при top-level fibs префикс обычно удерживается — значит O$n$.

Как получить контролируемое использование памяти

Если вам нужен только n-й элемент и вы не хотите хранить весь префикс, лучше использовать строгий итеративный алгоритм $константнаяпамятьподлинепрефикса$ или строгую свёртку. Примеры.

1) Строгая хвостовая рекурсия $O(n)времени,O(1)памяти$:

{-# LANGUAGE BangPatterns #-}
fib :: Int -> Integer
fib n = go n 0 1
where
go 0 !a _ = a
go k !a !b = go $k-1$ b $a+b$

$!-patternsгарантируют,чтоаккумуляторынебудутоставатьсяввидеthun{k}^{\prime }ов.$

2) foldl' вариант:

import Data.List $fold{l}^{\prime }$

fib n = fst $ foldl' ((a,b) _ -> (b, a+b)) (0,1) [1..n]

Этот вариант тоже O(n) времени, не накапливает thunk'ов благодаря foldl', но создаёт список [1..n] — можно заменить на явный цикл или использовать специализированные итераторы.

3) Если нужна ленивость + ограниченное кеширование, можно явным образом кэшировать только окно последних нескольких значений или хранить значения в массиве/vector и при необходимости освобождать старые элементы. Например, построить вектор длины n+1 и затем индексировать:

import qualified Data.Vector.Unboxed as VU
buildFibVec :: Int -> VU.Vector Integer
buildFibVec n = VU.create $ do
v <- VU.unsafeNew $n+1$ VU.unsafeWrite v 0 0
when (n >= 1) $VU.unsafeWritev11for{M}_{[}\mathrm{2..}n]$ \i -> do
a <- VU.unsafeRead v $i-2$ b <- VU.unsafeRead v $i-1$ VU.unsafeWrite v i $a+b$ return v

Этот подход использует O$n$ памяти, но она предсказуема и вы освобождаете вектор по завершении.

4) Если вы хотите сохранить ленивый infinite list, но избежать удержания старых элементов, не храните его в top-level CAF. Генерируйте список локально в месте использования и потребляйте его «стримингообразно» без сохранения ссылки на голову; тогда GC сможет освобождать пройденное. Но это ненадёжно и зависит от того, как именно используется список.

Резюме / рекомендации

Определение fibs = 0:1:zipWith $+$ fibs $tailfibs$ — удобно, лениво и с шеринго́м; хорошо, если вы хотите кешировать префикс и многократно читать одни и те же элементы.Если нужно контролируемое, предсказуемое использование памяти при доступе к n-му элементу, лучше использовать строгую хвостовую рекурсию или строгие свёртки $fold{l}^{\prime }$ — это даёт O$n$ время и O$1$ доп. памяти по длине префикса.Следите за типами $IntegervsInt$ и за тем, чтобы не накапливались thunk'и — используйте seq или BangPatterns или Data.Strict.Tuple, scanl' и т.п., когда нужно избежать отложенных вычислений.

Если хотите, могу привести конкретные варианты кода $сBangPatterns,сscan{l}^{\prime },сVector$ и измерения потребления памяти для разных n.