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

Свёртка и редукция

foldLeft и reduce

«Свёртка и редукция» — бесплатный урок 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 уроков всего.

Объединение элементов в одно значение

Иногда нужно объединить все элементы коллекции в одно значение, например сумму или конкатенацию. В Scala для этого предусмотрены fold, foldLeft, foldRight и reduce.

object Main {
  def main(args: Array[String]): Unit = {
    val nums = List(1, 2, 3, 4)
    println(nums.sum)
    println(nums.product)
  }
}

reduce: объединение без начального значения

reduce попарно объединяет элементы с помощью бинарной функции. Коллекция должна содержать как минимум один элемент, иначе будет выброшено исключение.

object Main {
  def main(args: Array[String]): Unit = {
    val nums = List(1, 2, 3, 4)
    val total = nums.reduce((a, b) => a + b)
    println(total)
    val max = nums.reduce((a, b) => if (a > b) a else b)
    println(max)
  }
}

foldLeft: объединение с начальным значением

foldLeft принимает начальное значение seed и функцию. Он безопасен для пустых коллекций (возвращает seed) и позволяет типу результата отличаться от типа элементов.

Синтаксис: xs.foldLeft(seed)((acc, x) => ...).

object Main {
  def main(args: Array[String]): Unit = {
    val nums = List(1, 2, 3, 4)
    val sum = nums.foldLeft(0)((acc, x) => acc + x)
    println(sum)
    val empty = List.empty[Int].foldLeft(0)(_ + _)
    println(empty)
  }
}

Шаблон с аккумулятором

В свёртке первый аргумент — это аккумулятор, в котором хранится текущий результат, а второй — текущий элемент. На каждом шаге аккумулятор обновляется.

object Main {
  def main(args: Array[String]): Unit = {
    val words = List("Scala", "is", "great")
    val sentence = words.foldLeft("")((acc, w) => acc + w + " ")
    println(sentence.trim)
  }
}

Тип результата может отличаться

Мощная особенность foldLeft: тип аккумулятора может отличаться от типа элементов. Здесь мы сворачиваем список чисел в String.

object Main {
  def main(args: Array[String]): Unit = {
    val nums = List(1, 2, 3)
    val joined = nums.foldLeft("nums:")((acc, n) => acc + " " + n)
    println(joined)
  }
}

foldRight: справа налево

foldRight обрабатывает элементы справа налево. Аккумулятор является вторым аргументом: (x, acc) => .... Направление имеет значение для некоммутативных операций.

object Main {
  def main(args: Array[String]): Unit = {
    val nums = List(1, 2, 3, 4)
    val left = nums.foldLeft("")((acc, x) => acc + x)
    val right = nums.foldRight("")((x, acc) => acc + x)
    println("foldLeft:  " + left)
    println("foldRight: " + right)
  }
}

Слева или справа: производительность

foldLeft реализован с хвостовой рекурсией и безопасен для стека при работе с большими списками. foldRight для List может привести к переполнению стека при очень больших входных данных. Предпочитайте foldLeft, если порядок обработки не требует иного.

object Main {
  def main(args: Array[String]): Unit = {
    val big = (1 to 100000).toList
    val total = big.foldLeft(0L)((acc, x) => acc + x)
    println(total)
  }
}

Построение коллекции с помощью fold

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

object Main {
  def main(args: Array[String]): Unit = {
    val nums = List(1, 2, 3, 4)
    val reversed = nums.foldLeft(List.empty[Int])((acc, x) => x :: acc)
    println(reversed)
  }
}

reduceOption для безопасности

Поскольку reduce завершается ошибкой для пустых коллекций, reduceOption вместо этого возвращает Option: Some(result) для непустой коллекции и None для пустой.

object Main {
  def main(args: Array[String]): Unit = {
    println(List(3, 1, 4).reduceOption(_ + _))
    println(List.empty[Int].reduceOption(_ + _))
  }
}

fold: симметричный вариант

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

object Main {
  def main(args: Array[String]): Unit = {
    val nums = List(1, 2, 3, 4)
    val total = nums.fold(0)(_ + _)
    println(total)
  }
}

Подсчёт с помощью foldLeft

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

object Main {
  def main(args: Array[String]): Unit = {
    val nums = List(4, 7, 2, 9, 6, 1)
    val evenCount = nums.foldLeft(0)((acc, x) => if (x % 2 == 0) acc + 1 else acc)
    println(s"even numbers: $evenCount")
  }
}

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

В чём главное различие между reduce и foldLeft?

Повторение

Вы изучили свёртку и сокращение:

reduce — попарно объединяет элементы, не использует начальное значение и завершается ошибкой для пустой коллекции
reduceOption — безопасный вариант, возвращающий Option
foldLeft — начальное значение и аккумулятор, безопасность стека, гибкий тип результата
foldRight — обработка справа налево; для больших списков следует учитывать размер стека
Свёртки позволяют даже создавать новые коллекции

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

Урок «Свёртка и редукция» бесплатный?

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

Чему я научусь в уроке «Свёртка и редукция»?

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

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

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

Сколько времени занимает урок «Свёртка и редукция»?

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

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

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

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

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