Scala for Backend Engineering & Functional Programming · レッスン

アキュムレーターのパターン

Q: 「アキュムレーターのパターン」で何を学びますか？

再帰中に状態を引き継ぎます。 ブラウザで直接実行するハンズオンコードでScala for Backend Engineering & Functional Programmingを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

再帰中に状態を引き継ぎます。

「アキュムレーターのパターン」はCoddyKit上の無料Scala for Backend Engineering & Functional Programmingレッスンです。これはレッスン2/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これは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)
}

アキュムレーターの実行

ここでは、アキュムレーターを使ってリストを合計する完全なプログラムを示します。

ベースケースが0ではなく、accを直接返している点に注目してください。リストを下っていく間に合計が構築されています。

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

2つの形を比較する

通常の再帰では、結合処理（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はこれをループに最適化し、1つのスタックフレームを再利用できます。そのため、どれほど深くてもスタックオーバーフローは発生しません。

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、リスト構築にはNil、文字列の連結には空文字列を使います。

初期値を間違えると、気付かないまま誤った結果になります。

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

結果の順序

アキュムレーターを使う再帰は要素を左から右へ処理しますが、先頭に追加するアキュムレーターでは要素の順序が反転します。

リストを構築しながら順序を保つ必要がある場合は、最後に反転するか、末尾に追加します。ただし、末尾への追加は低速です。通常は「先頭に追加してから反転」します。

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時間対応のAIチューター）、Scala for Backend Engineering & Functional Programmingコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Scala for Backend Engineering & Functional Programmingコースには全4レッスンが含まれています。

「アキュムレーターのパターン」で何を学びますか？

再帰中に状態を引き継ぎます。ブラウザで直接実行するハンズオンコードでScala for Backend Engineering & Functional Programmingを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Scala for Backend Engineering & Functional Programmingを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのScala for Backend Engineering & Functional Programmingは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン2/4です。

「アキュムレーターのパターン」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このScala for Backend Engineering & Functional Programmingレッスンでコードを書いて実行できますか？

はい。すべてのScala for Backend Engineering & Functional Programmingレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

再帰的に考える
アキュムレーターのパターン
foldLeftとfoldRight
reduceとaggregate

← Scala for Backend Engineering & Functional Programmingに戻る