アキュムレーターパターン
末尾再帰に変換します。
「アキュムレーターパターン」はCoddyKit上の無料Scala for Backend Engineering & Functional Programmingレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはScala for Backend Engineering & Functional Programming学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Scala for Backend Engineering & Functional Programmingコースには全4レッスンが含まれています。
アキュムレータパターン
アキュムレータパターンは、末尾再帰でない関数を末尾再帰に変換します。呼び出しから戻った後に結果を組み立てる代わりに、部分的な結果を追加のパラメーター（アキュムレーター）で引き渡します。
基本的な考え方
n + sum(n-1)のように呼び出し後に処理するのではなく、新しい部分合計を呼び出しの前に計算します。つまり、sum(n-1, acc + n)とします。これで再帰呼び出しが最後の処理になります。
変換前：末尾再帰でない合計
この直接的な実装は末尾再帰ではありません。加算が再帰呼び出しの完了を待つためです。
object Main {
def sum(n: Int): Int =
if (n == 0) 0 else n + sum(n - 1)
def main(args: Array[String]): Unit = {
println(sum(50))
}
}変換後：アキュムレーターを使った末尾再帰の合計
実行中の合計を保持するaccパラメーターを追加します。これで再帰呼び出しが末尾位置になり、最適化できるようになります。
import scala.annotation.tailrec
object Main {
@tailrec
def sum(n: Int, acc: Int = 0): Int =
if (n == 0) acc else sum(n - 1, acc + n)
def main(args: Array[String]): Unit = {
println(sum(50))
}
}末尾再帰の階乗
階乗にも同じ変換を適用します。再帰する前に、アキュムレーターへ乗算します。
import scala.annotation.tailrec
object Main {
@tailrec
def factorial(n: Int, acc: Long = 1): Long =
if (n <= 1) acc else factorial(n - 1, acc * n)
def main(args: Array[String]): Unit = {
println(factorial(10))
}
}アキュムレーターを隠す
追加したパラメーターは実装の詳細です。末尾再帰のワーカーを分かりやすい公開関数でラップし、呼び出し側からaccが見えないようにします。
import scala.annotation.tailrec
object Main {
def factorial(n: Int): Long = {
@tailrec
def loop(m: Int, acc: Long): Long =
if (m <= 1) acc else loop(m - 1, acc * m)
loop(n, 1)
}
def main(args: Array[String]): Unit = {
println(factorial(6))
}
}リストの累積
このパターンはコレクションの構築にも使えます。末尾再帰の反転処理では、各先頭要素をアキュムレーターのリストの先頭に追加します。
import scala.annotation.tailrec
object Main {
def reverse[A](xs: List[A]): List[A] = {
@tailrec
def loop(rem: List[A], acc: List[A]): List[A] = rem match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}
def main(args: Array[String]): Unit = {
println(reverse(List(1, 2, 3, 4)))
}
}累積の順序
アキュムレーターの先頭に追加すると、自然に順序が逆になる点に注意してください。順序を維持するリスト構築関数では、いったん逆順に構築して最後に反転するか、効率的な追加構造を使うことがよくあります。
末尾再帰のmap
アキュムレーターで結果のリストを構築し、最後に一度だけ反転して順序を戻します。
import scala.annotation.tailrec
object Main {
def mapTail[A, B](xs: List[A])(f: A => B): List[B] = {
@tailrec
def loop(rem: List[A], acc: List[B]): List[B] = rem match {
case Nil => acc.reverse
case h :: t => loop(t, f(h) :: acc)
}
loop(xs, Nil)
}
def main(args: Array[String]): Unit = {
println(mapTail(List(1, 2, 3))(_ * 10))
}
}foldLeftとの関係
アキュムレーターパターンは、foldLeftが一般化したものそのものです。foldLeftはアキュムレーターをコレクションに対して末尾再帰的に引き渡します。手動で書いたアキュムレーター関数の多くは、1つのfoldLeftに書き換えられます。
@main def run(): Unit = {
val total = List(1, 2, 3, 4).foldLeft(0)(_ + _)
println(total)
}使用する場面
再帰関数が大きな線形構造を処理し、そのままではスタックオーバーフローを起こす可能性がある場合に、アキュムレーターパターンを使用します。少し分かりにくい形になる代わりに、スタックセーフであることを保証できます。
理解度チェック
アキュムレーターパターンの理解度を確認しましょう。
まとめ
アキュムレーターパターンについて学びました。
- 追加のパラメーターで部分的な結果を引き渡します。
- 再帰する前に計算し、末尾位置に到達させます。
- 分かりやすい公開関数の背後にアキュムレーターを隠します。
foldLeftへ一般化できます。
よくある質問
「アキュムレーターパターン」レッスンは無料ですか？
はい。「アキュムレーターパターン」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと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は初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「アキュムレーターパターン」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このScala for Backend Engineering & Functional Programmingレッスンでコードを書いて実行できますか？
はい。すべてのScala for Backend Engineering & Functional Programmingレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 再帰の基礎
- tailrec アノテーション
- アキュムレーターパターン
- トランポリン