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?
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.