Свёртки: foldr и foldl

Свёртка (fold) — это «схлопывание» списка в одно значение: сумму, произведение, максимум, строку. Один шаблон на все случаи.

foldr вставляет операцию между всеми элементами: foldr (+) 0 [1,2,3] — это 1 + (2 + (3 + 0)). Узнаёте сумму?

Многие операции над списком сводят его к одному значению: сложить все числа, перемножить, найти максимум, склеить строки. Все они — частные случаи свёртки.

foldr: сворачиваем справа

foldr берёт бинарную функцию, начальное значение и список, и вставляет функцию между элементами, ассоциируя вправо:

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr (+) 0 [1, 2, 3]    -- 1 + (2 + (3 + 0)) = 6
foldr (*) 1 [1, 2, 3, 4] -- 24
foldr (:) [] [1, 2, 3]   -- [1,2,3] (копия списка)

foldr (+) 0 [1,2,3]
   1 + (2 + (3 + 0))
                   ^ начальное значение (0)
   = 6

foldl: сворачиваем слева

foldl ассоциирует влево, накапливая результат с начала:

foldl :: (b -> a -> b) -> b -> [a] -> b

foldl (+) 0 [1, 2, 3]    -- ((0 + 1) + 2) + 3 = 6

Для сложения результат тот же, но для несимметричных операций (вычитание, деление) направление важно. На практике для строгого накопления чаще берут foldl' — она не копит ленивые thunk'и и экономит память на больших списках.

Через свёртку выражаются и другие функции:

mySum     = foldr (+) 0
myProduct = foldr (*) 1
myLength  = foldr (\_ acc -> acc + 1) 0
myMax     = foldr1 max          -- foldr1 без начального значения

В Python прямой аналог — functools.reduce:

# Та же идея на Python: свёртка через reduce
from functools import reduce

total   = reduce(lambda acc, x: acc + x, [1, 2, 3], 0)
product = reduce(lambda acc, x: acc * x, [1, 2, 3, 4], 1)
print(total, product)          # 6 24

# reduce как foldl: накапливаем слева направо
maximum = reduce(lambda acc, x: x if x > acc else acc, [3, 7, 2, 9, 4])
print(maximum)                 # 9

Один шаблон на все агрегации

Свёртка — это, возможно, самая недооценённая новичками функция, хотя под ней скрыта почти любая агрегация. Сумма, произведение, максимум, подсчёт элементов, склейка строк, даже копирование списка — всё это частные случаи fold с разной операцией и разным начальным значением. Стоит увидеть это обобщение, и многие «ручные» рекурсивные функции окажутся свёрткой, написанной длинно. Начальное значение здесь играет двойную роль: это и стартовая точка накопления, и ответ для пустого списка, поэтому его подбирают как нейтральный элемент — ноль для суммы, единица для произведения. Между foldr и foldl выбирают по направлению и по эффективности: для строгих числовых накоплений на больших данных берут foldl', чтобы не плодить ленивые отложенки. Понимание свёрток открывает дверь и к более общим абстракциям вроде Foldable, работающим не только со списками.

Как это мыслить

Свёртка отвечает на вопрос: «как объединить два значения и с чего начать?». Дайте операцию (как соединять элемент и накопленное) и начальное значение (ответ для пустого списка) — и fold пройдёт по всему списку. Многие «ручные» циклы накопления — это замаскированная свёртка.

Стоит добавить, что идея свёртки выходит далеко за пределы списков. Класс типов Foldable обобщает её на множество структур данных — деревья, отображения, множества, — и одни и те же sum, maximum, toList работают для всех них. Поэтому, освоив свёртку на списках, вы фактически осваиваете универсальный язык агрегации, применимый к любым «контейнерам». Это типичный путь в Haskell: конкретное умение (свернуть список) оказывается частным случаем общей абстракции (свернуть любой Foldable), и однажды понятый узор начинает встречаться повсюду. Не торопитесь с обобщениями — сперва доведите до автоматизма свёртку списков, — но знайте, что за ней открывается куда более широкая и стройная картина, ради которой стоит держать fold в активном арсенале.

Частые ошибки

Неверное начальное значение. Для суммы это 0, для произведения 1; начальное — это «ответ для пустого списка».
Ленивый foldl на больших данных. Может накопить thunk'и; используйте foldl' из Data.List.
Путать порядок аргументов функции. У foldr аккумулятор — второй аргумент, у foldl — первый.

Best practices

Для большинства задач берите foldr с понятным начальным значением.
Для строгого числового накопления используйте foldl'.
Часто готовые sum, product, maximum уже выражены через свёртки — не изобретайте заново.

Итог. Свёртка схлопывает список в одно значение с помощью бинарной операции и начального значения. foldr ассоциирует вправо, foldl влево; для больших данных берите строгий foldl'. Это универсальный шаблон, обобщающий сумму, произведение, длину и многое другое.