scala - foldとfoldLeftメソッドの違い

Question

foldScalaとScalaの違いは何foldLeftですか。

質問foldとfoldLeftまたはfoldRightの違いは？注文について話している答えがあります。それは理解できます。しかし、私はまだこれがなぜ機能するのか理解していません（REPLから）：

scala> Array("1","2","3").foldLeft(0)(_ + _.toInt)
res6: Int = 6

しかし、これはしません：

scala> Array("1","2","3").fold(0)(_ + _.toInt)
<console>:8: error: value toInt is not a member of Any
              Array("1","2","3").fold(0)(_ + _.toInt)
                                               ^

このエラーメッセージはどういう意味ですか？

ドキュメントからのこの行も私を混乱させます。

z-折り畳み操作のニュートラル要素。結果には任意の回数追加でき、結果を変更してはなりません（たとえば、リストの連結の場合はNil、加算の場合は0、乗算の場合は1）。

なぜ任意の回数追加されるのですか？折りたたみの動作が違うと思いました。

Answer 1

Scala で定義されているように、foldLeftは線形操作foldですが、 はツリー操作が許可されています。例えば：

List(1,2,3,4,5).foldLeft(0)(_ + _)
// This is the only valid order of operations
0+1 = 1
      1+2 = 3
            3+3 = 6
                  6+4 = 10
                        10 + 5 = 15
                                 15  // done

List(1,2,3,4,5).fold(0)(_ + _)
// This is valid
0+1 = 1             0+3 = 3           0+5 = 5
      1+2 = 3             3+4 = 7           5
            3         +         7=10        5
                                  10    +   5 = 15
                                                15  // done

シーケンシャル リストの任意のツリー分解を可能にするには、何もしないゼロが必要です (ツリー内の必要な場所にゼロを追加できます)。バイナリ引数を使用して、ツリーの分解方法に応じて型が変化しないようにします。

(ツリーとして評価できることは、並列化に適しています。出力時間を途中で変換できるようにしたい場合は、組み合わせ演算子と標準の start-value-transforms-sequence-element-to-desired の両方が必要です。 -type 関数foldLeftは has と同じです。Scala には this があり、それを呼び出しますaggregateが、いくつかの点で、これはfoldLeft実際よりも似てfoldいます。)

Answer 2

私は Scala に詳しくありませんが、Scala のコレクション ライブラリは Haskell のものと似た設計になっています。この回答はHaskellに基づいており、おそらくScalaでも正確です。

入力を左から右に処理するためfoldLeft、入力と出力の型が異なる場合があります。一方、foldはさまざまな順序で入力を処理できるため、入力と出力はすべて同じ型でなければなりません。これは、fold 式を展開することで最も簡単に確認できます。 foldLeft特定の順序で動作します。

Array("1","2","3").foldLeft(0)(_ + _.toInt)
= ((0 + "1".toInt) + "2".toInt) + "3".toInt

配列要素は結合関数の最初のパラメータとして使用されないことに注意してください。これらは常に の右側に表示され+ます。

fold特定の順序を保証するものではありません。次のようなさまざまなことができます。

Array("1","2","3").fold(0)(_ + _.toInt)
=  ((0 + "1".toInt) + "2".toInt) + "3".toInt
or (0 + "1".toInt) + ("2" + "3".toInt).toInt
or "1" + ("2" + ("3" + 0.toInt).toInt).toInt

配列要素は、結合関数のいずれのパラメーターにも表示できます。ただし、結合関数は、最初の引数が int であることを想定しています。その制約を尊重しないと、文字列を int に追加することになります! このエラーは、型システムによってキャッチされます。

ニュートラル要素は複数回導入される可能性があります。これは、一般に、入力を分割して複数の順次フォールドを実行することにより、パラレル フォールドが実装されるためです。シーケンシャル フォールドでは、ニュートラル要素が 1 回導入されます。Array(1,2,3,4).fold(0)(_ + _)配列が 2 つの別個の配列に分割され、これらが 2 つのスレッドで順番に折りたたまれる特定の実行を想像してみてください。(もちろん、実際のfold関数は配列を複数の配列に吐き出しません。) 1 つのスレッドが を実行しArray(1,2).fold(0)(_ + _)、 を計算し0 + 1 + 2ます。もう一方のスレッドは を実行しArray(3,4).fold(0)(_ + _)、 を計算し0 + 3 + 4ます。最後に、2 つのスレッドからの部分合計が加算されます。ニュートラル要素0が 2 回出現することに注意してください。

Answer 3

注: ここでは完全に間違っている可能性があります。私のscalaは完璧ではありません。

違いはメソッドのシグネチャにあると思います：

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

対

def foldLeft[B](z: B)(op: (B, T) ⇒ B): B

要するに、fold は、配列の型のスーパータイプである型 A1 で動作するものとして定義されます。これは、文字列配列に対してコンパイラが「Any」として定義します (おそらく、文字列またはint-noticeを格納できる型が必要なためです)。 fold Fold に渡されたコンバイナ メソッドは、同じ型の 2 つのパラメータを受け取ることですか?) これは、z について説明するときにドキュメントが意味することでもあります。

"1" + "2" --\
             --> 3 + 3 -> 6
"3" + *z* --/

一方、 foldLeft はタイプ B (制約なし) で動作し、タイプ B のパラメーターと別の配列のタイプ (あなたの場合は String) を受け取り、B を生成するコンバイナー メソッドを提供することのみを要求します。

Answer 4

エラー。foldの署名では、コレクション内の値の型のスーパータイプである型の折りたたみ値のみが許可され、String(コレクション型) およびInt(提供されたゼロの型) の唯一のスーパータイプであるため、コンパイル時エラーが発生します。要素）がございAnyます。したがって、折り畳み結果の型はAny- であると推測されAny、メソッドはありませんtoInt。

の 2 つのバージョンのfoldシグネチャは異なることに注意してください。

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

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

なぜ彼らは異なる署名を持っているのですか? これはfold、並列コレクションの場合と同様に、並列で実装できるためです。複数のプロセッサがコレクション内の値をフォールド オーバーする場合、プロセッサのそれぞれが type の要素のサブセットを取得し、連続して を適用することによりA、type のフォールドされた値を生成します。これらのプロセッサによって生成された結果は、最終的な折り畳み値に結合する必要があります。これは、まさにそれを行う関数を使用して行われます。A1opop

fここで、これはinを使用して実行できないことに注意してください。これはfoldLeft、各プロセッサが type の折り畳まれた値を生成するためですB。型のいくつかの値をBを使用して結合することはできません。これは、値 を型の別の値とのみ結合するfためです。型との間には対応がありません。fBAAB

例。"1", "2"あなたの例では、最初のプロセッサが要素を取り、2番目のプロセッサが要素を取ると仮定します"3"。最初のものは折りたたまれた値を生成3し、2 番目のものは別の折りたたまれた値を生成します3。ここで、結果を結合して最終的な折り畳まれた値を取得する必要があります。これは不可能です。クロージャは 2 つの値ではなく、 andの_ + _.toInt結合方法しか認識していないためです。IntStringInt

これらの型が異なる状況ではaggregate、 type の 2 つの値を組み合わせる方法を定義する必要がある を使用しますB。

def aggregate[B](z: B)(seqop: (B, A) => B, combop: (B, B) => B): B

上記combopは、折り畳み結果とコレクション内の要素の型が異なる場合の最終ステップの実行方法を定義しています。

ニュートラルな要素。前述のように、複数のプロセッサがコレクション内の要素のサブセットを折りたたむ場合があります。それらのそれぞれは、ニュートラル要素を追加することによって折り畳まれた値を開始します.

次の例では:

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

常に戻ります10 = 4 + 1 + 2 + 3。

ただし、ニュートラルな要素ではないため、 と4一緒に使用しないでください。fold

List(1, 2, 3).fold(4)(_ + _)

上記は(4 + 1 + 2) + (4 + 3) = 14またはを返す場合があり(4 + 1) + (4 + 2) + (4 + 3) = 18ます。にニュートラル要素を使用しない場合fold、結果は非決定的になります。同様に、をニュートラル要素として使用できますが、Nil空でないリストは使用できません。

Answer 5

別の回答が指摘しているように、このfold方法は主に平行折りをサポートするために存在します。これは次のように見ることができます。まず、インスタンスで実行された操作を追跡できるようにする、整数の一種のラッパーを定義できます。

case class TrackInt(v: Int) {
  val log = collection.mutable.Buffer.empty[Int]
  def plus(that: TrackInt) = {
    this.log += that.v
    that.log += this.v
    new TrackInt(this.v + that.v)
  }
}

次に、これらのものとアイデンティティ要素の並列コレクションを作成できます。

val xs = (1 to 10).map(TrackInt(_)).par
val zero = TrackInt(0)

最初に試してみましょうfoldLeft:

scala> xs.foldLeft(zero)(_ plus _)
res0: TrackInt = TrackInt(55)

scala> zero.log
res1: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1)

foldLeftシーケンシャル フォールドを実行するため、予想どおり、0 の値は 1 回だけ使用されます。次に、ログをクリアして試すことができますfold:

scala> zero.log.clear()

scala> xs.fold(zero)(_ plus _)
res2: TrackInt = TrackInt(55)

scala> zero.log
res3: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 6, 2, 7, 8)

したがって、ゼロ値が複数回使用されるようにフォールドが並列化されていることがわかります。これをもう一度実行すると、ログに異なる値が表示される可能性があります。

Answer 6

一般的な違い

ここにメソッドのプロトタイプがあります

fold[A1 >: A](z: A1)(op: (A1, A1) ⇒ A1): A1
foldLeft[B](z: B)(f: (B, A) ⇒ B): B

したがって、fold の場合、結果はA1 >: Aany ではなくtype になりますB。さらに、ドキュメントで指定されているようにfold、注文はそうではありません

エラーについて

入力するときは、 anが のサブタイプであるscala> Array("1","2","3").fold(0)(_ + _.toInt)と想定します。これが、コンパイラがエラーをスローする理由です。0intString

折り畳みの奇妙な z について

ここで、何が起こるかを理解するために の実装を確認する必要があります。fold得られるものは次のとおりです。

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

つまり、基本的には、出力タイプに制約foldのあるの実装です。が実際には と同じように使用されることがfoldleftわかります。したがって、将来の実装での動作を保証するものは何もないため、このコメントが作成されたと結論付けることができます。parallelsを使用して、すでにそれを見ることができます。zfoldleft

def fold[U >: T](z: U)(op: (U, U) => U): U = {
  executeAndWaitResult(new Fold(z, op, splitter))
}