Scala for Backend Engineering & Functional Programming · Урок

foldLeft и foldRight

Сворачивайте коллекции в одно значение.

Урок 3 из 413 шагов

«foldLeft и foldRight» — бесплатный урок Scala for Backend Engineering & Functional Programming на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Scala for Backend Engineering & Functional Programming, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Scala for Backend Engineering & Functional Programming содержит 4 уроков всего.

Свёртка коллекции

Свёртка объединяет коллекцию в одно значение, последовательно объединяя элементы с аккумулятором.

Освоенный Вами шаблон с аккумулятором — именно то, что абстрагирует fold. Вместо самостоятельного написания рекурсивной вспомогательной функции Вы передаёте начальное значение и функцию объединения.

Основы foldLeft

foldLeft принимает начальный аккумулятор и функцию (acc, element), а затем проходит коллекцию слева направо.

На каждом шаге он заменяет аккумулятор результатом функции.

val xs = List(1, 2, 3, 4)
val total = xs.foldLeft(0)((acc, x) => acc + x)

@main def run(): Unit =
  println(total)  // 10

Как работает ассоциативность foldLeft

foldLeft расставляет скобки слева. Для List(1, 2, 3) с начальным значением z он вычисляет f(f(f(z, 1), 2), 3).

Аккумулятор является левым аргументом, поэтому он накапливается по мере движения вправо по списку.

// List(1, 2, 3).foldLeft(0)(_ + _)
// = ((0 + 1) + 2) + 3
// = 6

Основы foldRight

foldRight также объединяет элементы, но начинает справа.

Его функция принимает (element, acc): элемент находится слева, а аккумулятор — справа.

val xs = List(1, 2, 3, 4)
val total = xs.foldRight(0)((x, acc) => x + acc)

@main def run(): Unit =
  println(total)  // 10

Как работает ассоциативность foldRight

foldRight расставляет скобки справа. Для List(1, 2, 3) с начальным значением z он вычисляет f(1, f(2, f(3, z))).

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

// List(1, 2, 3).foldRight(0)(_ + _)
// = 1 + (2 + (3 + 0))
// = 6

Когда направление имеет значение

Для ассоциативных и коммутативных операций, таких как сложение или умножение, обе свёртки дают одинаковый результат.

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

val xs = List(1, 2, 3)
val l = xs.foldLeft(0)(_ - _)   // ((0-1)-2)-3 = -6
val r = xs.foldRight(0)(_ - _)  // 1-(2-(3-0)) = 2

@main def run(): Unit =
  println((l, r))  // (-6, 2)

Построение списка

foldRight естественно подходит для восстановления списка в исходном порядке, поскольку работает от хвоста внутрь, а добавление в начало сохраняет расположение элементов.

Так каждый элемент преобразуется с сохранением порядка.

val xs = List(1, 2, 3)
val doubled = xs.foldRight(List.empty[Int]) { (x, acc) =>
  (x * 2) :: acc
}

@main def run(): Unit =
  println(doubled)  // List(2, 4, 6)

foldLeft разворачивает список

Если строить список с помощью foldLeft и добавлять элементы в начало, результат окажется перевёрнутым, поскольку элементы добавляются спереди по мере движения вправо.

Иногда именно это и требуется.

val xs = List(1, 2, 3)
val rev = xs.foldLeft(List.empty[Int]) { (acc, x) =>
  x :: acc
}

@main def run(): Unit =
  println(rev)  // List(3, 2, 1)

Безопасность стека

foldLeft является хвостовой рекурсией и работает как цикл, поэтому безопасен для очень больших коллекций.

foldRight для List не является хвостовой рекурсией и может переполнить стек на очень длинных списках. Если порядок справа налево не нужен, предпочитайте foldLeft.

// Safe even for millions of elements:
val n = (1 to 1000000).foldLeft(0L)(_ + _)

// foldRight on a long List risks StackOverflowError

Изменение типа результата

Тип аккумулятора может отличаться от типа элементов.

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

Тип свёртки определяется начальным значением.

val xs = List(1, 2, 3)
val s = xs.foldLeft("")((acc, x) => acc + x.toString)

@main def run(): Unit =
  println(s)  // "123"

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

Многие операции над списками являются частными случаями свёртки: sum, product, length, max, map, filter, reverse.

Понимание лежащей в их основе свёртки помогает писать краткий декларативный код вместо рекурсии, написанной вручную.

val xs = List(4, 1, 7, 3)
val maxV = xs.foldLeft(Int.MinValue)(_ max _)
val len  = xs.foldLeft(0)((acc, _) => acc + 1)

@main def run(): Unit =
  println((maxV, len))  // (7, 4)

Быстрая проверка

Рассуждайте о направлении свёртки и положении начального значения.

Ответь в интерактивном уроке

Итоги

foldLeft проходит слева направо, помещая аккумулятор слева, и вычисляет ((z op a) op b) op c. Это хвостовая рекурсия, безопасная для стека.

foldRight проходит справа налево, помещая начальное значение справа, и вычисляет a op (b op (c op z)). Он подходит для построения списка с сохранением порядка, но может переполнить стек на длинных списках.

Начальное значение определяет тип результата, поэтому свёртки могут преобразовать коллекцию в любое значение.

Можно начать бесплатно

Изучай Scala с ИИ-репетитором — бесплатно

Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.

Курсы: 39
Уроки: 143

Начать учиться бесплатно Посмотреть полный курс

Часто задаваемые вопросы

Урок «foldLeft и foldRight» бесплатный?

Да — полный текст урока «foldLeft и foldRight» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Scala for Backend Engineering & Functional Programming, подпишись на CoddyKit PRO. Курс Scala for Backend Engineering & Functional Programming содержит 4 уроков всего.

Чему я научусь в уроке «foldLeft и foldRight»?

Сворачивайте коллекции в одно значение. Ты практикуешь Scala for Backend Engineering & Functional Programming с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Scala for Backend Engineering & Functional Programming?

Предыдущий опыт не требуется. Scala for Backend Engineering & Functional Programming на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «foldLeft и foldRight»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Scala for Backend Engineering & Functional Programming?

Да. Каждый урок Scala for Backend Engineering & Functional Programming включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к Scala for Backend Engineering & Functional Programming