fold, reduce и агрегация

Если `map` преобразует каждый элемент, то `fold` схлопывает всю коллекцию в одно значение.

«Свёртка — это аккордеон наоборот: множество значений складывается в одно по заданному правилу.»

Часто нужно превратить целую коллекцию в одно число или объект: сумму, произведение, максимум. Для этого служит свёртка (fold). foldLeft идёт слева направо, неся с собой накопленное значение (аккумулятор).

val nums = List(1, 2, 3, 4)

val sum = nums.foldLeft(0)((acc, x) => acc + x)      // 10
val product = nums.foldLeft(1)((acc, x) => acc * x)  // 24
println(sum)
println(product)

Первый аргумент foldLeft(0) — начальное значение аккумулятора. Функция получает текущий аккумулятор и элемент, возвращает новый аккумулятор.

foldLeft(0)(+)  по List(1,2,3,4):
  acc=0,  x=1 -> 1
  acc=1,  x=2 -> 3
  acc=3,  x=3 -> 6
  acc=6,  x=4 -> 10
  результат -> 10

reduce — свёртка без начального значения

reduce похож на foldLeft, но берёт первый элемент как стартовый аккумулятор. Поэтому на пустой коллекции он падает — будьте осторожны.

val nums = List(4, 2, 7, 1)
val max = nums.reduce((a, b) => if a > b then a else b)  // 7
val total = nums.reduce(_ + _)                           // 14

Готовые агрегаты

Для частых случаев есть готовые методы — они короче и понятнее ручного fold.

val nums = List(1, 2, 3, 4, 5)
println(nums.sum)       // 15
println(nums.max)       // 5
println(nums.min)       // 1
println(nums.count(_ > 2))  // 3 — сколько больше двух

Та же идея на Python ▶

# fold/reduce на Python через functools.reduce
from functools import reduce

nums = [1, 2, 3, 4]
total = reduce(lambda acc, x: acc + x, nums, 0)   # 10, как foldLeft(0)
product = reduce(lambda acc, x: acc * x, nums, 1) # 24
print(total, product)

# готовые агрегаты
print(sum(nums), max(nums), min(nums))
print(sum(1 for x in nums if x > 2))   # count(_ > 2) = 2

Как работает под капотом (JVM)

foldLeft реализован как обычный цикл с одной изменяемой локальной переменной-аккумулятором — несмотря на функциональный вид снаружи. Это эффективно и не растит стек. Важно различать foldLeft и foldRight: foldRight идёт с конца и для List может быть рекурсивным и медленным на больших данных (риск переполнения стека). Поэтому на практике предпочитают foldLeft. Готовые sum, max внутри тоже сводятся к свёртке.

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

reduce на пустой коллекции. Он бросит исключение; используйте foldLeft с начальным значением, если коллекция может быть пустой.
Перепутать порядок в функции fold. Для foldLeft аккумулятор — первый аргумент, элемент — второй.
Брать foldRight на больших списках. Это медленно и рискует переполнить стек.

Best practices

Для агрегации с возможной пустотой используйте foldLeft с явным стартом.
Где есть готовый метод (sum, max, count) — берите его, он понятнее.
Предпочитайте foldLeft foldRight для списков из соображений производительности.

Свёртка как универсальный инструмент

Свёртка — недооценённо мощная операция. На первый взгляд это просто способ посчитать сумму, но на деле foldLeft может выразить почти любую агрегацию: подсчёт, поиск максимума, группировку, построение строки, даже разворот списка. Всё, что «проходит по коллекции, накапливая результат», — это свёртка. Освоив её, вы получаете один инструмент, заменяющий десяток специализированных циклов.

Понимание разницы между foldLeft и foldRight — признак зрелого владения Scala. foldLeft идёт слева и реализован как эффективный цикл, поэтому безопасен на больших данных. foldRight идёт справа и для списков рекурсивен, что грозит переполнением стека. На практике почти всегда выбирают foldLeft, а где есть готовый агрегат вроде sum или count — берут его ради читаемости. Свёртка остаётся запасным инструментом для случаев, которых нет среди готовых методов.

Чтобы свёртка стала интуитивной, полезно мысленно проговаривать её как «начни с этого значения и на каждом элементе делай вот так». Эта формулировка сразу подсказывает и стартовое значение, и функцию-комбинатор. Когда вы научитесь видеть агрегацию в таких терминах, многие задачи, прежде требовавшие цикла со счётчиком, будут решаться одной строкой свёртки.

Итоги. foldLeft сворачивает коллекцию в одно значение, неся аккумулятор; reduce делает то же без старта (опасен на пустых); есть готовые sum/max/count. Дальше — for-выражения, объединяющие всё это.