This is not true.
> def List[A].foldLeft[B](z: B)(op: (B, A) => B): B
> def List[A].foldRight[B](z: B)(op: (A, B) => B): B
Notice the signature of the fold op: the arguments types are swapped. This is because fold left and right on a list [a, b], say, is the difference between:
(z op a) op b
and
a op (b op z)
(If this isn't compelling enough, consider [a, b, c].) Not all functions are associative. For example, consider a cryptographic hash function.
If you're saying that foldRight in scala exists aesthetic reasons... well can't argue with that. I figured it was more for legacy reasons as the original poster said that there use to be a performance difference.
As for the associative thing I mentioned side effects. Function composition is always associative. Unless you have side effects. See: https://www.wikiwand.com/en/Function_composition (search for associative)
I don't know much about crypto but I'm assuming you're referring to things that aren't side effect free. In general though a hash function should be associative under function composition as it is just a surjective mapping from domain to codomain.
Also can't exactly read that syntax nor the stuff below it. Not a scala dude. Maybe a more traditional map implementation in like python or JS pseudo code would make more sense to me, but that may be too much to ask.
edit:
I think you actually may be right. We're both a little wrong with our reasoning though. Function composition is not commutative. And FoldRight and FoldLeft reverses the order of composition which has an effect on operations that are not commutative.
// this makes a linked list ten million and one elements long, from zero to ten million
val longList = (0 to 10000000).toList
// this adds the elements
longList.foldRight(0)({ case (l, r) => l + r})
This does not stack overflow.
You write:
>> a plain fold has the exact same inputs and outputs as foldLeft or foldRight
but if you use fold over a collection of type T with the fold function in Scala, the result must be of type T. Fold left and fold right don't have this constraint. Further, this fold is only coherent if the operation is commutative, because it doesn't happen in any particular order. You can add integers in any order to make the same sum, but you can't add pages of a PDF in any order to make a PDF.
Framed via recursion schemes, I'm pretty sure foldLeft can be viewed as a catamorphism where foldRight is an anamorphism. You're consuming the tree from different directions. They may have the same domain and codomain (I'm a little hazy on that) but they're not apparently the same function. y = 2x and y = 3x both have the same domain and codomain, right? But the difference between them isn't aesthetic.
You're wrong about the operations possibly not being commutative; as you pointed out, whether the parameter list is (A, B) or (B, A) doesn't really matter, so it doesn't pose a problem.
An example is the subtraction operator: with just two elements, I can change `(a, b) => b - a` to `(b, a) => b - a` with with no difference in result. But there is no way I can write a subtraction function for foldLeft that gives the same results as a foldRight on subtraction in general. That is, I can write op such that a op b = b - a, but not that (a op b) op c = (c - b) - a. Nevertheless, I can still write op such that a op (b op c) = (c - b) - a due to some dual notion of commutativity.
So in essence given three functions z,g,f and composition operator <.>
f . g . z != z . g . f (commutativity)
but:
f . g . z == z . (g . f) (associativity)
Function composition isn't completely accurate to what's going on, it's a more higher order form of composition going on with fold but the rules remain the same.
Whatever, either way, Overall I'm wrong
You're still confused. There is no function composition here.
op in the example above is just some other function, like +. The associativity of + and function composition are true for totally unrelated reasons. Associativity of plus is an inductive argument that follows from the Peano axioms.
Function composition says:
(f o g) o h = f o (g o h)
as functions. It is true because unary function application "serializes" function applications. Formally, I mean:
((f o g) o h)(x)
= f(g(h(x)))
= (f o (g o h))(x)
Intuitively the composition is similar enough to function composition that is has the same basic ruleset and is how I'm working out the logic in my head. Think of the functor as a tuple of the accumulator and the value: (acc, x), and the function is just an op that takes in this tuple as a parameter and spits out a new tuple (acc, z) with the next value in the list.
I addressed it earlier here: https://news.ycombinator.com/item?id=24449271