[解決済み] 関数型プログラミング（特にScalaとScala API）におけるreduceとfoldLeft/foldの違いとは？

質問

なぜScalaとSparkやScaldingのようなフレームワークには、両方とも reduce と foldLeft ? では、その違いは何かというと reduce と fold ?

どのように解決するのですか？

reduceとfoldLeftの比較

このトピックに関連する他の stackoverflow の回答では明確に言及されていない、大きな大きな違いは、次のとおりです。 reduce を与えるべきであるということです。 可換モノイド すなわち、可換かつ連想である演算が与えられるべきです。 これは、演算が並列化できることを意味します。

この区別は、ビッグデータ/MPP/分散コンピューティングにとって非常に重要であり、その理由の全ては reduce が存在する理由でもあります。 コレクションは切り刻むことができ reduce はそれぞれの塊に対して操作することができ、その後 reduce は各チャンクの結果を操作することができます。実際、チャンキングのレベルは1つのレベルにとどまる必要はありません。 各チャンクを切り刻むこともできるのです。 これが、無限の CPU がある場合、リスト内の整数の合計が O(log N) である理由です。

シグネチャを見るだけでは reduce で実現できることは、すべて reduce で foldLeft . の機能は foldLeft の方が reduce .

しかし を並列化することはできません。 foldLeft を並列化できないので、その実行時間は常に O(N) です（可換モノイドを投入しても）。これは、演算が ではなく でないため、累積値は一連の逐次集約によって計算されるからです。

foldLeft は可換性も連想性も仮定しません。 コレクションを切り刻むことができるのは連想性であり、順序が重要でない（つまり、各チャンクからの結果をどの順序で集約するかは問題ではない）ため、累積を簡単にするのは可換性です。厳密に言えば、並列化、たとえば分散ソート アルゴリズムには可換性は必要なく、チャンクに順序を与える必要がないため、ロジックが簡単になるだけです。

に関するSparkのドキュメントを参照すると reduce を見ると、特に "... commutative and associative binary operator" と書いてあります。

http://spark.apache.org/docs/1.0.0/api/scala/index.html#org.apache.spark.rdd.RDD

以下はその証明です。 reduce の単なる特別な場合ではないことを証明しています。 foldLeft

scala> val intParList: ParSeq[Int] = (1 to 100000).map(_ => scala.util.Random.nextInt()).par

scala> timeMany(1000, intParList.reduce(_ + _))
Took 462.395867 milli seconds

scala> timeMany(1000, intParList.foldLeft(0)(_ + _))
Took 2589.363031 milli seconds

reduce vs fold

ここからは、FP/数学のルーツに少し近くなり、説明するのが少し難しくなります。 Reduce は MapReduce パラダイムの一部として正式に定義されており、秩序のないコレクション (マルチセット) を扱います。Fold は再帰の観点から正式に定義されており (カタモーフィズムを参照)、したがってコレクションに構造/シーケンスを仮定しています。

は存在しません。 fold メソッドはありません。なぜなら（厳密な）Map Reduceプログラミングモデルでは fold を定義できないからです。 fold は連想性だけを要求し、可換性は要求しないからです。

簡単に言うと reduce は累進の順序なしに動作します。 fold は累積の順序が必要で、その累積の順序がゼロ値を必要とするのであって、ゼロ値の存在が両者を区別しているのではありません。 厳密には reduce でなければなりません。 は空のコレクションで動作します。なぜなら、そのゼロ値は任意の値を取ることで推論できるからです x を解き x op y = x を解きますが、これは非可換演算ではうまくいきません。なぜなら、左と右で異なるゼロ値が存在しうるからです（すなわち x op y != y op x ). もちろん，Scalaはこのゼロ値が何であるかを調べようとはしません．なぜなら，それには（おそらく計算不可能な）いくつかの数学が必要になるからです．

プログラミングにおける明らかな違いはシグネチャだけなので，（語源でよくあるように）この本来の数学的な意味は失われてしまったようです．その結果 reduce の同義語になっています。 fold の同義語になりました。むしろ、MapReduceからの元の意味を保存しています。現在、これらの用語はしばしば互換的に使用され、ほとんどの実装で同じように動作します（空のコレクションは無視されます）。Sparkのような特殊性によって奇妙さが悪化していますが、これから対処します。

そこでSparkは は は fold がありますが、サブ結果（各パーティションに1つずつ）が結合される順序は、（執筆時点では）タスクが完了する順序と同じであり、したがって非決定論的なのです。という指摘をしてくれた @CafeFeed に感謝します。 fold は runJob を使用していますが、コードを読んだ後、それが非決定的であることに気づきました。さらに混乱を招いたのは、Sparkが treeReduce があるのに treeFold .

結論

という違いがあります。 reduce と fold は、空でない配列に適用された場合でも 前者はMapReduceプログラミングパラダイムの一部として、任意の順序を持つコレクションに対して定義されています ( http://theory.stanford.edu/~sergei/papers/soda10-mrc.pdf。 ) で定義されており、決定論的な結果を得るためには、演算子が連想的であることに加えて可換であることを仮定する必要があります。後者は同型性で定義され、コレクションがシーケンスの概念を持っている（またはリンクリストのように再帰的に定義されている）ことが必要で、したがって、可換演算子は必要ではありません。

プログラミングの非数学的な性質により、実際には reduce と fold は同じように動作する傾向があり、（Scalaのように）正しく動作することもあれば、（Sparkのように）正しく動作しないこともあります。

おまけ。Spark APIに関する私の意見

私の意見としては、もし fold という用語が Spark で完全に削除されれば、混乱は避けられると思います。 少なくとも、Spark は彼らのドキュメントに注釈を入れています。

これは、Scalaのような関数型言語で非分散コレクションに対して実装されたfold操作とは多少異なる挙動をします。 Scalaのような関数型言語で非分散コレクションに実装されているfold操作とは多少異なる動作をします。