Is foldRight equivalent to foldLeft given a non-commutative associative operation?

Question

The online course stated that foldLeft and foldRight equivalent for operators that are associative and commutative .

One of the students is categorical that such operators should only be associative. Therefore, this property must be true for operations such as composing functions and matrix multiplication.

As far as I can argue, an associative operation that is not commutative will not give equivalent results for foldLeft and foldRight , unless z is neutral, and the operation accumulates in such a way that the order of the operands remains intact. IMO operation should be commutative in the general case.

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

So, for foldLeft and foldRight equivalent if operation both associative and commutative, or is it enough that operation associative?

Answer 1

The function must be both commutative and associative.

If our function is f , and our elements are x1 - x4 , then:

foldLeft f(f(f(x1, x2), x3), x4)

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

Let us use the middle function, which is commutative, but not associative ( (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 

EDITOR: I missed the boat only associatively, but only commutatively. See @jwvy string concatenation example for an associative but not commutative function.

Answer 2

String concatenation ("abc" + "xyz") is associative, but not commutative, and foldLeft / foldRight will put the source / zero element at the opposite ends of the resulting string. If this null item is not an empty string, the results are different.

Answer 3

foldLeft (...(z op x1)... op xn) foldRight x1 op (x2 op (... xn op z)...) Thus, op must be commutative and associative so that these two are equivalent in the general case

Answer 4

There are at least three relevant cases with separate answers:

• In the general case, when op: (B, A) -> B or op: (A, B) -> B , as in the foldLeft and foldRight , neither associativity nor foldRight are defined.

• If B >: A and z is a two-way identifier op: (B, B) -> B and op is associative , then for all L.foldLeft(z)(op) type List[A] , L.foldLeft(z)(op) returns the same result as and L.foldRight(z)(op) .

  This is closely related to the fact that if B >: A and op: (B, B) -> B , then if op associative, for all L.reduceLeft(op) type List[A] L.reduceLeft(op) the same result is returned that and L.reduceRight(op) .

• If B >: A and op: (B, B) -> B are associative and commutative , then for all L type List[A] and z type B , L.foldLeft(z)(op) returns the same result as and L.foldRight(z)(op) .