What good are right-associative methods in Scala?

Question

I've just started playing around with Scala, and I just learned about how methods can be made right-associative (as opposed to the more traditional left-associativity common in imperative object-oriented languages).

At first, when I saw example code to cons a list in Scala, I had noticed that every example always had the List on the right-hand side:

println(1 :: List(2, 3, 4))
newList = 42 :: originalList

However, even after seeing this over and over again, I didn't think twice about it, because I didn't know (at the time) that :: is a method on List. I just assumed it was an operator (again, in the sense of operator in Java) and that associativity didn't matter. The fact that the List always appeared on the right-hand side in example code just seemed coincidental (I thought it was maybe just the "preferred style").

Now I know better: it has to be written that way because :: is right-associative.

My question is, what is the point of being able to define right-associative methods?

Is it purely for aesthetic reasons, or can right-associativity actually have some kind of benefit over left-associativity in certain situations?

From my (novice) point-of-view, I don't really see how

1 :: myList

is any better than

myList :: 1

but that's obviously such a trivial example that I doubt it's a fair comparison.

Answer 1

The short answer is that right-associativity can improve readability by making what the programmer type consistent with what the program actually does.
So, if you type '1 :: 2 :: 3', you get a List(1, 2, 3) back, instead of getting a List back in a completely different order.
That would be because '1 :: 2 :: 3 :: Nil' is actually

List[Int].3.prepend(2).prepend(1)

scala> 1 :: 2 :: 3:: Nil
res0: List[Int] = List(1, 2, 3)

which is both:

• more readable
• more efficient (O(1) for prepend, vs. O(n) for an hypothetic append method)

---

(Reminder, extract from the book Programming in Scala)
If a method is used in operator notation, such as a * b, the method is invoked on the left operand, as in a.*(b) — unless the method name ends in a colon.
If the method name ends in a colon, the method is invoked on the right operand.
Therefore, in 1 :: twoThree, the :: method is invoked on twoThree, passing in 1, like this: twoThree.::(1).

For List, it plays the role of an append operation (the list seems to be appended after the '1' to form '1 2 3', where in fact it is 1 which is prepended to the list).
Class List does not offer a true append operation, because the time it takes to append to a list grows linearly with the size of the list, whereas prepending with :: takes constant time.
myList :: 1 would try to prepend the entire content of myList to '1', which would be longer than prepending 1 to myList (as in '1 :: myList')

Note: No matter what associativity an operator has, however, its operands are always evaluated left to right.
So if b is an expression that is not just a simple reference to an immutable value, then a ::: b is more precisely treated as the following block:

{ val x = a; b.:::(x) }

In this block a is still evaluated before b, and then the result of this evaluation is passed as an operand to b’s ::: method.

---

why make the distinction between left-associative and right-associative methods at all?

That allows to keep the appearance of a usual left-associative operation ('1 :: myList') while actually applying the operation on the right expression because;

• it is more efficient.
• but it is more readable with an inverse associative order ('1 :: myList' vs. 'myList.prepend(1)')

So as you say, "syntactic sugar", as far as I know.
Note, in the case of foldLeft, for instance, they might have gone a little to far (with the '/:' right-associative operator equivalent)

---

To include some of your comments, slightly rephrased:

if you consider an 'append' function, left-associative, then you would write 'oneTwo append 3 append 4 append 5'.
However, if it were to append 3, 4, and 5 to oneTwo (which you would assume by the way it's written), it would be O(N).
Same with '::' if it was for "append". But it is not. It is actually for "prepend"

That means 'a :: b :: Nil' is for 'List[].b.prepend(a)'

If '::' were to prepend and yet remain left-associative, then the resulting list would be in the wrong order.
You would expect it to return List(1, 2, 3, 4, 5), but it would end up returning List(5, 4, 3, 1, 2), which might be unexpected to the programmer.
That is because, what you have done would have been, in the left-associative order:

(1,2).prepend(3).prepend(4).prepend(5) : (5,4,3,1,2)

So, the right-associativity makes the code match up with the actual order of the return value.

Answer 2

What is the point of being able to define right-associative methods?

I think the point of right-associative method is to give someone an opportunity to extend the language, which is the point of operator overriding in general.

Operator overloading is a useful thing, so Scala said: Why not open it up to any combination of symbols? Rather, why make distinction between the operators and methods? Now, how does a library implementor interact with built-in types like Int? In C++, she would have used friend function in the global scope. What if we want all types to implement the operator ::?

The right-associativity gives a clean way to add :: operator to all types. Of course, technically the :: operator is a method of List type. But it's also a make-believe operator for built-in Int and all of the other types, at least if you could ignore the :: Nil at the end.

I think it reflects Scala's philosophy of implementing as much things in the library and making the language flexible to support them. This allows an opportunity for someone to come up with SuperList, which could be called as:

1 :: 2 :: SuperNil

It's somewhat unfortunate that the right associativity is currently hard-coded only to the colon at the end, but I guess it makes it easy enough to remember.

Answer 3

Right-associativity and Left-associativity plays an important role when you are performing List fold operations. For eg:

def concat[T](xs: List[T], ys: List[T]): List[T] = (xs foldRight ys)(_::_)

This works perfectly fine. But you cannot perform the same using foldLeft operation

def concat[T](xs: List[T], ys: List[T]): List[T] = (xs foldLeft ys)(_::_)

,because :: is right-associative.