给定非交换结合运算，foldRight 是否等同于 foldLeft？

Question

在线课程中指出 foldLeft 和 foldRight 对于 结合和交换的运算符是等价的。

其中一名学生坚持认为此类运算符只需要结合即可。所以这个属性应该适用于函数组合和矩阵乘法等操作。

据我所知，不可交换的关联运算不会为 foldLeft 和 foldRight 产生等效结果，除非 z 是中性的并且该运算累积在这样操作数的顺序保持不变。 IMO 在一般情况下操作必须是可交换的。

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

那么，要使 foldLeft 和 foldRight 等价，operation 应该同时具有结合性和交换性，还是 operation 具有结合性就足够了？

Answer 1

函数必须同时具有交换性和结合性。

如果我们的函数是f，我们的元素是x1到x4，那么：

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 将放置 initial/zero 元素在结果字符串的两端。如果该零元素不是空字符串，则结果不同。

Answer 3

foldLeft 是 (...(z op x1)... op xn) foldRight 是 x1 op (x2 op (... xn op z)...) 所以 op 需要是可交换的和结合的，两者在一般情况下是等价的

Answer 4

至少有三个相关案例有不同的答案：

在 op: (B, A) -> B 或 op: (A, B) -> B 的一般情况下，如 foldLeft 和 foldRight 的签名中，既没有定义结合性也没有定义交换性.
如果B >: A和z是op: (B, B) -> B和op的双面身份是关联那么对于类型 List[A]、L.foldLeft(z)(op) returns 的所有 L 与 L.foldRight(z)(op).[= 相同的结果37=]
这与以下事实密切相关：如果 B >: A 和 op: (B, B) -> B 那么，如果 op 是关联的，对于类型 List[A] 的所有 L L.reduceLeft(op) returns 与 L.reduceRight(op).
相同的结果
如果 B >: A 和 op: (B, B) -> B 都是 关联和交换 那么对于 L 类型的所有 List[A] 和 B 类型的 z、L.foldLeft(z)(op) returns 与 L.foldRight(z)(op).
的结果相同

给定非交换结合运算，foldRight 是否等同于 foldLeft？

Is foldRight equivalent to foldLeft given a noncommutative associative operation?

scala

fold

equivalent