Коротко: выражение
$\text{sum}=\text{foldl}(+)0[\mathrm{1..10000000}]$
построит длинную цепочку отложенных вычислений (thunks) вида
$(\dots ((0+1)+2)+3)\cdots +10000000$,
в результате — сильная утечка памяти (и/или переполнение стека при последующей оценке). Строгая версия foldl' не накапливает такие отложенные выражения и работает в постоянной памяти.
Почему так происходит (сжато):
- foldl определён как (упрощённо)
foldl f z (x:xs) = foldl f (f z x) xs.
Но из‑за ленивости Haskell вызов $fzx$ не вычисляется сразу — вместо этого накапливается thunk. После n шагов результат выглядит как вложенное невычисленное выражение $(\dots ((0+1)+2)+\cdots +n)$.
- Когда в конце вы требуете результат (print или evaluate), интерпретатор пытается постепенно раскрывать этот большой thunk. Раскрытие может потребовать большой стек/память и привести к stack overflow или OutOfMemory.
- foldl' (в Data.List) делает строгую оценку аккумулятора на каждом шаге — по сути она делает seq или использует "!" (bang) — поэтому аккумулятор сразу сводится к WHNF, и thunks не накапливаются. Это даёт амортизированную O(1) память.
Как выглядит строгий шаг (упрощённо):
foldl' f acc (x:xs) = let acc' = f acc x in acc' `seq` foldl' f acc' xs
Комментарии о (+) и типах:
- Даже если (+) сам по себе строг в аргументах для Int, это не спасает: если аккумулятор — thunk, то вызов (+) с этим thunk не будет выполнен, если вы его не заставите вычислить. Именно поэтому нужно строго вычислять аккумулятор, а не полагаться на строгость оператора.
Практические тесты и профилирование (рекомендуемые шаги)
1) Минимальные программы
sum_lazy.hs:
import System.IO
main = print (foldl (+) 0 [1..10000000])
sum_strict.hs:
import Data.List (foldl')
main = print (foldl' (+) 0 [1..10000000])
2) Компиляция и запуск с выводом статистики RTS:
ghc -O2 sum_lazy.hs -o sum_lazy
ghc -O2 sum_strict.hs -o sum_strict
./sum_lazy +RTS -s
./sum_strict +RTS -s
Сравните строки "maximum residency", "bytes allocated", "productivity". Ожидаемо: lazy — много аллокаций/большая резидентность или даже крах; strict — мало памяти, быстрая работа.
3) Профайлинг по месту аллокации (heap profile)
ghc -O2 -prof -fprof-auto -rtsopts sum_strict.hs
./sum_strict +RTS -hc -p -RTS
Посмотрите .hp (heap profile) и .prof (time profile) файлы с помощью hp2ps или других инструментов. Это покажет, где происходит распределение памяти и подтверждает, что lazy-версия тратит память на thunks.
4) Отладка в GHCi
- В GHCi можно экспериментировать на меньших списках и смотреть :sprint и контроль evaluate (Control.Exception.evaluate). Это помогает увидеть накопление thunks.
5) Дополнительные тесты
- Повторите тесты для типов Int и Integer (Integer может увеличивать память дополнительно из‑за больших bignum).
- Сравните с Prelude.sum (в разных версиях может быть определён по‑разному) и с реализацией через foldr/scanl.
- Проверьте поведение при компиляции без -O2 (поведение strictness может отличаться).
Выводы кратко:
- foldl накапливает отложенные вычисления — приводит к росту памяти/стеку.
- foldl' заставляет аккумулятор вычисляться немедленно и избегает утечек.
- При численных агрегациях всегда предпочтительна строгая свёртка (foldl' или специализированные функции), либо использовать структуры/алгоритмы, гарантирующие немедленную оценку.