What good are right-associative methods in Scala?

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


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.

Leave a Comment