foldLeftとfoldRight
コレクションを1つの値にまとめます。
「foldLeftとfoldRight」は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レッスンが含まれています。
コレクションを畳み込む
畳み込みとは、アキュムレーターを使って要素を繰り返し結合し、コレクションを1つの値にまとめることです。
学習したアキュムレーターパターンを抽象化したものが、まさに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) // 10foldLeftの結合順序
foldLeftは左から括ります。シードをzとしたList(1, 2, 3)では、f(f(f(z, 1), 2), 3)を計算します。
アキュムレーターが左側の引数になるため、リストを右へ進みながら値を蓄積します。
// List(1, 2, 3).foldLeft(0)(_ + _)
// = ((0 + 1) + 2) + 3
// = 6foldRightの基本
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) // 10foldRightの結合順序
foldRightは右から括ります。シードをzとしたList(1, 2, 3)では、f(1, f(2, f(3, z)))を計算します。
シードは最も右に置かれ、リストは末尾から内側に向かって結合されます。
// List(1, 2, 3).foldRight(0)(_ + _)
// = 1 + (2 + (3 + 0))
// = 6方向が重要な場合
合計や積のような結合的かつ交換可能な演算では、どちらのfoldでも同じ結果になります。
減算やリスト構築のように交換できない演算では、方向によって結果が変わります。意図的に選択してください。
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は末尾再帰でループとして実行されるため、非常に大きなコレクションでも安全です。
Listに対するfoldRightは末尾再帰ではなく、非常に長いリストではスタックオーバーフローが発生する可能性があります。右から左への順序が不要ならfoldLeftを優先してください。
// Safe even for millions of elements:
val n = (1 to 1000000).foldLeft(0L)(_ + _)
// foldRight on a long List risks StackOverflowError結果の型を変える
アキュムレーターの型は要素の型と異なっていても構いません。
ここでは整数のリストを文字列に畳み込むため、シードは空文字列で、各ステップで追加します。
foldの型はシードによって決まります。
val xs = List(1, 2, 3)
val s = xs.foldLeft("")((acc, x) => acc + x.toString)
@main def run(): Unit =
println(s) // "123"万能ツールとしてのfold
多くのリスト操作はfoldの特殊なケースです。合計、積、長さ、最大値、map、filter、reverseなどが該当します。
これらの内部にあるfoldを見抜くと、手作業の再帰ではなく、簡潔で宣言的なコードを書けるようになります。
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)理解度チェック
foldの方向とシードの位置について考えてみましょう。
まとめ
foldLeftはアキュムレーターを左側に置いて左から右へ進み、((z op a) op b) op cを計算します。末尾再帰であり、スタック安全です。
foldRightはシードを右側に置いて右から左へ進み、a op (b op (c op z))を計算します。順序を保ったリスト構築に適していますが、長いリストではスタックオーバーフローが発生する可能性があります。
シードが結果の型を決めるため、foldを使ってコレクションを任意の値へ変換できます。
AI チューターと学ぶ Scala — 無料
ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。
- コース
- 39
- レッスン
- 143
よくある質問
「foldLeftとfoldRight」レッスンは無料ですか？
はい。「foldLeftとfoldRight」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Scala for Backend Engineering & Functional Programmingコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Scala for Backend Engineering & Functional Programmingコースには全4レッスンが含まれています。
「foldLeftとfoldRight」で何を学びますか？
コレクションを1つの値にまとめます。 ブラウザで直接実行するハンズオンコードでScala for Backend Engineering & Functional Programmingを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Scala for Backend Engineering & Functional Programmingを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのScala for Backend Engineering & Functional Programmingは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「foldLeftとfoldRight」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このScala for Backend Engineering & Functional Programmingレッスンでコードを書いて実行できますか？
はい。すべてのScala for Backend Engineering & Functional Programmingレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 再帰的に考える
- アキュムレーターのパターン
- foldLeftとfoldRight
- reduceとaggregate