foldReftと同等のfoldRightは、非可換の連想操作で与えられますか？

Question

オンラインコースでfoldLeftとfoldRightは、の関連語句と同等です。

学生のうちの1人は、そのような演算子が連想する必要があることを強く示しています。したがって、このプロパティは、関数の構成や行列の乗算のような演算に対して真でなければなりません。

限りzは中立で、操作は、オペランドの順序は手つかずのままであるように蓄積されていない限り、私はfoldLeftとfoldRightのための同等の結果が得られないだろう可換ではない連想動作を言うことができるように。 IMOは一般的なケースでは可換でなければならない。

list.foldLeft(z)(operation) == list.foldRight(z)(operation) 

だから、 foldLeftと foldRightため operation同時に連想と可換であるべきと同等であることや、それが operationのために十分に連想されるのですか？

Answer 1

この関数は可換性と結合性の両方でなければなりません。

私たちの機能がfあり、そして私たちの要素は、その後、x1x4にある場合：

foldLeftがあるf(f(f(x1, x2), x3), x4)

foldRightあるf(x1, f(x2, f(x3, x4)))

のは可換ではなく連想ではない平均的機能を、使用してみましょう（(a + b)/2 == (b + a)/2）：

scala> def avg(a: Double, b: Double): Double = (a + b)/2 
avg: (a: Double, b: Double)Double 

scala> (0 until 10).map(_.toDouble).foldLeft(0d)(avg) 
res4: Double = 8.001953125 

scala> (0 until 10).map(_.toDouble).foldRight(0d)(avg) 
res5: Double = 0.9892578125 

編集：私は唯一の交換に対決でボートを逃した。 @ jwvyの連想ではなく可換関数の文字列連結の例を参照してください。

Answer 2

String連結（「ABC」+「XYZ」）が連想が、可換ではなく、foldLeft/foldRight結果の文字列の両端に初期/ゼロ要素を配置します。そのゼロ要素が空の文字列でない場合、結果は異なります。

Answer 3

foldLeftは(...(z op x1)... op xn) foldRightは、2つの一般的なケースでは同等であるためには可換と連想するx1 op (x2 op (... xn op z)...) のでopニーズである

Answer 4

あり、別の答えと、少なくとも3関連の例です：

は、

1. op: (B, A) -> Bまたはop: (A, B) -> Bの場合、foldLeftおよびfoldRightというシグネチャのように、結合性も可換性も定義された。

2. はB >: Aとz場合op: (B, B) -> Bとopの両面同一あるL.foldRight(z)(op)と同じ結果を返すL.foldLeft(z)(op)タイプList[A]の全てL、次いでため連想あります。

   これは密接opタイプの全てLため、連想ある場合、B >: Aとop: (B, B) -> B場合、List[A]L.reduceLeft(op)はL.reduceRight(op)と同じ結果を返すことに関連しています。

3. B >: A場合、及びop: (B, B) -> BはL.foldRight(z)(op)と同じ結果を返すL.foldLeft(z)(op)、タイプList[A]及びタイプBのzの全てL、次いで連想と可換の両方です。