Scalaの折りたたみリスト

1. 序章

このチュートリアルでは、さまざまなアプローチを使用してScalaでリストを折りたたむ方法を見ていきます。 Listクラスのfold関数は、リスト内のデータ、初期値、および結合関数を受け取ります。

次に、リスト内の要素をステップスルーし、提供された関数をそれらに適用します。 必要に応じて、3つの折りたたみ機能のいずれかを使用できます。 fold 、foldLeftまたはfoldRight。

これらの関数はすべて同じように動作しますが、ルールとユースケースが異なり、最適な場合があります。

2. 折りたたみ

リストはコアScalaの一部であるため、リストを折りたたむために特別な設定は必要ありません。 ただし、 foldを使用するには、Scala2.9以降が必要です。 foldLeftとfoldRightは、以前のScalaバージョンに存在します。

ウィキペディアの定義を言い換えると、フォールディングでは、高階関数を使用して再帰的なデータ構造を分析し、特定の結合操作を適用することで、サブパーツの処理結果を再結合し、戻り値を作成します。

val list = List(1, 2, 3, 4, 5)
val sum = list.fold(0)((x, y) => x + y)
assert(sum == 15)Copy

foldメソッドは2セットの引数を取ります。 1つには開始値が含まれ、もう1つには結合関数が含まれます。 次にはリストをステップ実行し、関数を2つのオペランド（累積値とリスト内の次の要素）に再帰的に適用します。

最初のステップでは、開始値0が最初のオペランドとして機能します。 リストの最初の要素は、2番目のオペランドとして機能します。 この計算の結果は、次のステップの最初のオペランドになり、リストの2番目の要素である2番目のオペランドになります。

その後の手順では、リスト内の次の要素を結合関数の2番目のオペランドとして使用し続けます。リストの最後まで、累積値はいずれの場合も最初のオペランドのままです。

Step 1: x(0) + y(1) = 1
Step 2: x(1) + y(2) = 3
Step 3: x(3) + y(3) = 6
Step 4: x(6) + y(4) = 10
Step 5: x(10) + y(5) = 15 Copy

fold で使用できるオプションを見ていくときに、簡単なオブジェクトを紹介してみましょう。

case class Person(name: String, sex: String)Copy

そして、左または右の折りたたみをテストするためのこれらのオブジェクトのリスト：

val persons = List(Person("Thomas", "male"), Person("Sowell", "male"), Person("Liz", "female"))Copy

3. foldLeft

foldLeftはリストを左から右に繰り返し、要素をこの順序で蓄積します。 これは、結合関数の2つのオペランドを処理する場合、アキュムレータが左側の引数であることも意味します。

val foldedList = persons.foldLeft(List[String]()) { (accumulator, person) =>
  val title = person.sex match {
    case "male" => "Mr."
    case "female" => "Ms."
  }
  accumulator :+ s"$title ${person.name}"
}
assert(foldedList == List("Mr. Thomas", "Mr. Sowell", "Ms. Liz"))Copy

最終リストの要素の方向に注意してください。

より正式には、foldLeftは左側に関連付けられます。 アキュムレータが初期化され、要素が左から右の順序で追加されます。

List(1, 2, 3).foldLeft(0)(f) = f(f(f(0, 1), 2), 3)Copy

4. foldRight

一方、 foldRightは、リストを右から左に繰り返し、要素をこの順序で蓄積します。 逆に、これは、各反復でアキュムレータが右側のオペランドになることを意味します。

val foldedList = persons.foldRight(List[String]()) { (person, accumulator) =>
  val title = person.sex match {
    case "male" => "Mr."
    case "female" => "Ms."
  }
  accumulator :+ s"$title ${person.name}"
}
assert(foldedList == List("Ms. Liz", "Mr. Sowell", "Mr. Thomas"))Copy

また、最終リストの要素の順序にも注意してください。 より正式には、foldRightは右側に関連付けられます。 つまり、アキュムレータが初期化され、要素は右から左の順序で蓄積されます。

List(1, 2, 3).foldRight(0)(f) = f(1, f(2, f(3, 0)))Copy

5. 折り畳み

foldLeftとfoldRightは線形操作ですが、foldはツリー操作にすることができます。つまり、処理順序は保証されません。 リストを任意の順序でサブセットに分解できます。 次に、これらを個別に評価し、結果をまとめて最終結果を得ることができます。

foldメソッドは主に並列処理をサポートするために存在します。

5.1. 並列処理

いくつかの非常に単純なケースでは、3つの折りたたみ機能すべてが同じように機能する可能性があり、違いを検出できない場合があります。 これは、リスト、出力、および初期値がすべて同じタイプである場合に明らかです。

List(1, 2, 3, 4, 5).fold(0)(_ + _)
List(1, 2, 3, 4, 5).foldLeft(0)(_ + _)
List(1, 2, 3, 4, 5).foldRight(0)(_ + _)Copy

上記のすべての行で同じ結果が得られます。 ただし、それらの内部実行を掘り下げると、いくつかの明白な違いがわかります。 まず、リストを並列化して、foldが意図した魔法を実行できるようにします。 並列化しないと、foldLeftのように機能します。 最初の例のように：

val parallelNumSeq = List(1, 2, 3, 4, 5).parCopy

コンバイナ関数のパラメータの名前に細心の注意を払う必要があります。

foldLeft との合計：

val foldLeftResult =
  parallelNumSeq.foldLeft(0) { (acc, currNum) =>
    val sum = acc + currNum
    println(s"FoldLeft: acc($acc) + currNum($currNum) = $sum ")
    sum
  }
println(foldLeftResult)Copy

蓄積は左から右に行われます。 印刷された結果を見ると、さらに明確になります。

FoldLeft: acc(0) + currNum(1) = 1 
FoldLeft: acc(1) + currNum(2) = 3 
FoldLeft: acc(3) + currNum(3) = 6 
FoldLeft: acc(6) + currNum(4) = 10 
FoldLeft: acc(10) + currNum(5) = 15 
15Copy

foldRight との合計：

val foldRightResult = 
  parallelNumSeq.foldRight(0) { (currNum, acc) =>
    val sum = acc + currNum
    println(s"FoldRight: acc($acc) + currNum($currNum) = $sum")
    sum
  }
println(foldRightResult)Copy

今回は右から左に折ります。 結果：

FoldRight: acc(0) + currNum(5) = 5
FoldRight: acc(5) + currNum(4) = 9
FoldRight: acc(9) + currNum(3) = 12
FoldRight: acc(12) + currNum(2) = 14
FoldRight: acc(14) + currNum(1) = 15
15Copy

最後に、foldと合計しましょう。

val foldResult = parallelNumSeq.fold(0) { (acc1, acc2) =>
    val sum = acc1 + acc2
    println(s"Fold: acc1($acc1) + acc2($acc2) = $sum")
    sum
  }
println(foldResult)Copy

実際、並列モードでは、コンバイナー関数の両方のパラメーターはアキュムレーターです。これらは両方とも、リストのサブセットに対して実行された順次foldの結果である可能性があるためです。

Fold: acc1(0) + acc2(1) = 1
Fold: acc1(0) + acc2(4) = 4
Fold: acc1(0) + acc2(2) = 2
Fold: acc1(0) + acc2(5) = 5
Fold: acc1(0) + acc2(3) = 3
Fold: acc1(4) + acc2(5) = 9
Fold: acc1(1) + acc2(2) = 3
Fold: acc1(3) + acc2(9) = 12
Fold: acc1(3) + acc2(12) = 15
15Copy

初期値（ 0 ）が数回使用されているのに対し、最初の2つのケースでは、1回だけ使用され、折り畳みが順番に進行することに注意してください。

5.2. メソッドシグネチャ

3つの折り目の違いをさらに理解するために、それらの署名を見てみましょう。

fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1

foldLeft[B](z: B)(f: (B, A) => B): BCopy

foldRight[B](z: B)(f: (A, B) => B): B

3つすべてのフォールドで、開始値zと戻り値BまたはA1は、同じタイプである必要があります。 ただし、具体的には、タイプAのListの場合、foldLeftおよびfoldRightはタイプBの結果を返します。 ここで、 B は、 A と同じタイプ、 A に関連するタイプ、またはAに関連しないタイプの場合があります。

宣言では、AとBの間に関係は定義されていません。

val stringifiedInts = List("1", "2", "3", "4", "5")
val foldLeftSum = stringifiedInts.foldLeft(0)((acc, currNum) => acc + currNum.toInt)
val foldRightSum = stringifiedInts.foldRight(0)((currNum, acc) => currNum.toInt + acc)
assert(foldLeftSum == 15)
assert(foldRightSum == 15)Copy

前の例では、リストのタイプは Int。でした。上記の例では、リストのタイプはStringです。 このタイプは、foldLeftとfoldRightの両方の署名でAで表されます。 ここで扱っている唯一の制約は、開始値とアキュムレータの両方が同じタイプであるということです。 結合関数がタイプの違いを処理できる限り、リストタイプが何であるかは関係ありません。

これは折り畳みには当てはまりません。 開始値と結果は、折りたたむリストと同じタイプまたはスーパータイプである必要があります。 の中に折り畳みサイン、 A にバインドされている型変数ですリスト[+A] 。 これは、合計の例では、Aが Int であり、制約を満たしていることを意味します。

fold に対するこの制約と、foldLeftおよびfoldRightに対するその欠如は、前述の順序の保証に関連付けられています。foldは使用できません結合機能fは、BとAが同じ順序で提供されることを常に保証するという契約を尊重できないため、1回の呼び出しでBを提供できます。 Aの代わりにを使用します。その逆も同様です。

5.3. ニュートラル要素

すでに説明したように、 fold を使用すると、最終的な結果は、ニュートラル要素を追加することから始まる複数の連続した折り畳みを組み合わせた結果になります。 最初の例から：

List(1, 2, 3, 4, 5).foldLeft(5)(_ + _)Copy

これにより、一貫して20が返されます。

5 + 1 + 2 + 3 + 4 + 5 = 20Copy

ただし、 0 以外は、ニュートラルまたはゼロ要素ではなく、一貫性のない結果を返すため、foldと一緒に使用しないでください。 加算の中立要素は0、であり、これが積または乗算演算の場合、1になります。

List(1, 2, 3).fold(5)(_ + _)Copy

上記の例では、次のようになります。

(5 + 1 + 2) + (5 + 3) = 16Copy

または、他の何か：

(5 + 1) + (5 + 2) + (5 + 3) = 21Copy

6. 結論

この記事では、Scalaでリストを折りたたむためのさまざまなアプローチについて説明しました。 いつものように、完全なソースコードはGitHubでから入手できます。