Scala and the :: object

Question

I've been diving into scala, and am absolutely loving it so far. I'm getting around to pattern matching and case classes, and the following has me somewhat stumped. I know what it does, but I want to understand exactly what is happening

var list = List(2,3,4)
1::list

If I am correct in my understanding so far. Then the :: represents a case object. If so my question is:

how am I "left applying" it to the 1? instead of :: being a method of 1. Basically can someone pull this statement 1::list apart somewhat, showing what is really happening (ie. what methods are being called on what object)

Thanks

Answer 1

It's annoying that some of the most visible and awesome features of Scala have so much complexity right beneath the surface. So, consider this simple line:

val (head :: tail): ::[Int] = 1 :: Nil

Each of the three places where :: appears refers to a different ::, and a different mechanism in Scala. Let's go through each of them, in order.

head :: tail

What is happening here is pattern matching, just like one sees with case statements. Pattern matching can appear on val assignments, on the left side of <- in for comprehensions, and on case statements.

So, how does this particular pattern matching happens? Well, whenever the pattern is in the format a b c, Scala translates this into b(a, c), which is then translated into calls to unapply or unapplySeq on the object b.

So, :: in val (head :: tail) refers to the object :: (defined through a case class).

: ::[Int]

This is a type declaration, so ::[Int] is a type. :: itself is a class, and a type constructor as well (because it constructs types given a type parameter -- ::[Int] is one type, ::[String] is another type, etc). It is also a subclass of List, which has only two subclasses: :: and the singleton class of Nil.

This declaration is superfluous, and, generally speaking, one hardly ever uses :: as a type or class. I show it here mostly for completeness.

1 :: Nil

Here, :: is a method. It is a method of List, so, since Nil is a List and 1 is not, it must belong to Nil (or be available through implicit conversion).

The mechanism of note here is that methods ending with :, when used in infix operator notation, bind to the right instead of to the left. Or, in other words, a :: b is equivalent to b.::(a).

This mechanism is rarely used and, I suspect, made mostly to make traditional fp list algorithms more familiar to programmers used to fp. It is used in a few other places on Scala standard library and out of it.

On Scala 2.8, for instance, there's now +:, which serves the same purpose of ::, but is defined for all Seq. It is mirrored by :+, which appends elements, and whose : serves no purpose other than disambiguate it from +, which is overloaded to concatenate strings.

Answer 2

An operator name ending in : binds to the right. :: [A] is really a case class and a subclass of List[A], as can be seen in the Scala API reference. :: is also a method operating on its right argument, a list, taking its left operand as an argument and returning a ::[A].

So, in your example, the method :: is called on list with 1 as an argument. This constructs an object of type :: [Int] with arguments 1 and list.

Answer 3

The very quick answer. The method :: is being called on list with 1 as the parameter.

Any method name (and yes, :: is a method) that ends in a colon operates on the right operand.

Answer 4

To add some additional information to the other answers:

:: is both a subclass of List

final case class ::[B](private var hd: B, private[scala] var tl: List[B]) extends List[B] { ... }

and a method on List

def ::[B >: A] (x: B): List[B] = new scala.collection.immutable.::(x, this)

which is basically implemented in terms of the first one.

So there is no deep theoretical background behind this one, just keep in mind the rule about methods ending with :.

Answer 5

My understanding of :: (the "cons" operator) is that it is used in this manner because prepending an element to a list (technically, creating a new list with the new element prepended to the old list) is of O(1) , whereas appending it would be of O(N). It's an efficiency thing...