Is foldRight equivalent to foldLeft given a noncommutative associative operation?

Question

In a online course it was stated that foldLeft and foldRight are equivalent for operators that are associative and commutative.

One of the students is adamant that such operators only need to be associative. So this property should be true for operations like function composition and matrix multiplication.

As far as I can tell an associative operation that isn't commutative will not produce equivalent results for foldLeft and foldRight unless z is neutral and the operation is accumulated in such a way that the order of the operands remains untouched. IMO the operation has to be commutative in the general case.

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

So, for foldLeft and foldRight to be equivalent should operation be simultaneously associative and commutative or is it enough for operation to be associative?

Answer 1

String concatenation ("abc" + "xyz") is associative but not commutative and foldLeft/foldRight will place the initial/zero element at opposite ends of the resulting string. If that zero element is not the empty string then the results are different.

Answer 2

The function must be both commutative and associative.

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

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

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

Let's use the average 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

EDIT: I missed the boat on only associative vs only commutative. See @jwvy's example of string concatenation for an associative but not commutative function.