В Scala (и других функциональных языках) fold, reduce и scan — это методы для агрегации элементов коллекции. Они принимают бинарную функцию и применяют её последовательно ко всем элементам коллекции, сворачивая (редуцируя) их в одно значение. Несмотря на похожую идею, между ними есть существенные различия в начальных значениях, возврате промежуточных результатов и устойчивости к пустым коллекциям.

reduce

reduce — это метод, который сворачивает коллекцию в одно значение, применяя бинарную функцию. При этом не задаётся начальное значение, и в качестве первого аргумента используется первый элемент коллекции.

Сигнатура:

def reduce\[A1 >: A\](op: (A1, A1) => A1): A1

Пример:

val list = List(1, 2, 3, 4)
val result = list.reduce(_ + \_) // 10

reduce работает только с непустыми коллекциями. Если список пуст, будет выброшено исключение.

Поток операций:

(((1 + 2) + 3) + 4) → 10

fold

fold — более гибкий, т.к. принимает начальное значение и безопасен для пустых коллекций. Начальное значение используется как стартовое накопленное значение.

Сигнатура:

def fold\[B\](z: B)(op: (B, A) => B): B

• z — начальное значение типа B

• op — функция, которая принимает аккумулятор и элемент

Пример:

val list = List(1, 2, 3, 4)
val result = list.fold(0)(_ + \_) // 10

Поток операций:

(((0 + 1) + 2) + 3) + 4 → 10

Пример с другим типом:

val result = list.fold("Start:")((acc, x) => acc + " " + x)
// "Start: 1 2 3 4"

Вариации:

• foldLeft — проход слева направо (обычно используемый)

• foldRight — справа налево (может быть менее эффективным из-за рекурсии)

List(1, 2, 3).foldLeft(0)(_ - \_) // (((0 - 1) - 2) - 3) = -6
List(1, 2, 3).foldRight(0)(_ - \_) // (1 - (2 - (3 - 0))) = 2

scan

scan — это то же самое, что fold, но возвращает все промежуточные значения аккумулятора, а не только итоговое.

Сигнатура:

def scan\[B\](z: B)(op: (B, A) => B): collection.Seq\[B\]

• Возвращает коллекцию, включающую z и каждый шаг накопления.

Пример:

val list = List(1, 2, 3)
val result = list.scan(0)(_ + \_)
// Vector(0, 1, 3, 6)

• Сначала 0 (начальное значение)

• 0 + 1 = 1

• 1 + 2 = 3

• 3 + 3 = 6

Применение:

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

Сравнение всех трёх:

Ещё примеры

reduce:

List(5, 2, 8).reduce((a, b) => if (a > b) a else b) // 8

fold:

List("a", "b", "c").fold("")(_ + \_) // "abc"

scan:

List(1, 2, 3, 4).scan(1)(_ \* \_) // Vector(1, 1, 2, 6, 24)

Резюме различий на коде

val data = List(1, 2, 3)
// reduce
val r = data.reduce(_ + \_) // 6
// fold
val f = data.fold(0)(_ + \_) // 6
// scan
val s = data.scan(0)(_ + \_) // Vector(0, 1, 3, 6)

scan полезен, когда нужно отследить путь к результату. fold — гибкий и безопасный, идеален для любых случаев. reduce — самый короткий по записи, но только для непустых коллекций.