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

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

Передавайте состояние через рекурсию.

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

Зачем нужны аккумуляторы

Обычная рекурсия строит результат при возврате вверх по стеку вызовов, после завершения рекурсивного вызова.

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

Этот небольшой сдвиг открывает путь к хвостовой рекурсии и постоянному использованию стека.

Вспомогательная функция

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

Внешняя функция лишь запускает её с начальным значением, часто равным 0 или пустому списку.

def sum(xs: List[Int]): Int = {
  def loop(rest: List[Int], acc: Int): Int = rest match {
    case Nil    => acc
    case h :: t => loop(t, acc + h)
  }
  loop(xs, 0)
}

Работа аккумулятора

Здесь полная программа суммирует список с помощью аккумулятора.

Обратите внимание: базовый случай напрямую возвращает acc, а не 0. Итог накапливался по мере продвижения вниз по списку.

def sum(xs: List[Int]): Int = {
  def loop(rest: List[Int], acc: Int): Int = rest match {
    case Nil    => acc
    case h :: t => loop(t, acc + h)
  }
  loop(xs, 0)
}

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

Сравнение двух структур

В обычной рекурсии шаг объединения (h + ...) ждёт завершения внутреннего вызова.

В варианте с аккумулятором объединение выполняется до вызова, а сам вызов становится последним действием функции.

Именно это свойство последнего вызова делает рекурсию хвостовой.

// Plain: combine after the call
case h :: t => h + sum(t)

// Accumulator: combine before the call
case h :: t => loop(t, acc + h)

Хвостовая рекурсия

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

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

import scala.annotation.tailrec

@tailrec
def countDown(n: Int): Unit =
  if (n < 0) ()
  else { println(n); countDown(n - 1) }

Аннотация @tailrec

Добавление @tailrec просит компилятор проверить, действительно ли функция является хвостовой рекурсией.

Если это не так, компиляция завершается понятной ошибкой. Так скрытая ловушка производительности превращается в гарантию, проверяемую во время сборки.

import scala.annotation.tailrec

def sum(xs: List[Int]): Int = {
  @tailrec
  def loop(rest: List[Int], acc: Int): Int = rest match {
    case Nil    => acc
    case h :: t => loop(t, acc + h)
  }
  loop(xs, 0)
}

@main def run(): Unit = println(sum((1 to 100000).toList))

Накопление списка

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

Эта функция reverse добавляет каждую голову в начало аккумулятора, естественным образом меняя порядок. Добавление в начало с помощью :: выполняется быстро, поэтому такой подход эффективен.

def reverse[A](xs: List[A]): List[A] = {
  def loop(rest: List[A], acc: List[A]): List[A] = rest match {
    case Nil    => acc
    case h :: t => loop(t, h :: acc)
  }
  loop(xs, Nil)
}

Работа reverse

Аккумулятор начинается пустым и растёт по мере обработки входных данных.

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

def reverse[A](xs: List[A]): List[A] = {
  def loop(rest: List[A], acc: List[A]): List[A] = rest match {
    case Nil    => acc
    case h :: t => loop(t, h :: acc)
  }
  loop(xs, Nil)
}

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

Несколько аккумуляторов

Вспомогательная функция может одновременно передавать несколько аккумуляторов.

Здесь в одном цикле отслеживаются текущее произведение и количество элементов, а результат возвращается в виде кортежа.

Каждый аккумулятор передаёт своё обновлённое значение в следующий вызов.

def stats(xs: List[Int]): (Int, Int) = {
  def loop(rest: List[Int], prod: Int, count: Int): (Int, Int) =
    rest match {
      case Nil    => (prod, count)
      case h :: t => loop(t, prod * h, count + 1)
    }
  loop(xs, 1, 0)
}

Выбор начального значения

Начальное значение аккумулятора должно быть нейтральным элементом используемой операции.

Для сложения используйте 0, для умножения — 1, для построения списка — пустой список, а для объединения строк — пустую строку.

Неправильное начальное значение незаметно приводит к неверным ответам.

// addition  -> seed 0
// product   -> seed 1
// list      -> seed Nil
// string    -> seed ""

Порядок результатов

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

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

def mapInc(xs: List[Int]): List[Int] = {
  def loop(rest: List[Int], acc: List[Int]): List[Int] = rest match {
    case Nil    => acc.reverse
    case h :: t => loop(t, (h + 1) :: acc)
  }
  loop(xs, Nil)
}

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

Выберите верное утверждение о рекурсии с аккумулятором.

Итоги

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

Это помещает рекурсивный вызов в хвостовую позицию, позволяя оптимизировать хвостовые вызовы в Scala и выполнять проверку безопасности с помощью @tailrec.

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

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

Урок «Шаблоны с аккумулятором» бесплатный?

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

Чему я научусь в уроке «Шаблоны с аккумулятором»?

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

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

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

Сколько времени занимает урок «Шаблоны с аккумулятором»?

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

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

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

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

  1. Рекурсивное мышление
  2. Шаблоны с аккумулятором
  3. foldLeft и foldRight
  4. reduce и агрегация
← Назад к Scala for Backend Engineering & Functional Programming