Why is scala list class named ::

Question

Why is the scala list implementation named :: and not a class name? Is there some special meaning behind that?

Answer 1

A linked list is composed of two cases: a cons cell (with a head and a tail), and the empty list. These cases are called :: and Nil respectively in Scala, as in other languages with ML heritage. In an immutable implementation, the most natural encoding looks something like this:

sealed trait List[+A]

case class Cons[+A](head: A, tail: List[A]) extends List[A]
case object Nil extends List[Nothing]

This works just fine and there's really nothing wrong with it. You can define a :: method on List (or prepend, if you prefer), and things work exactly as you would expect. In this case, the "concrete implementation" of List will be Cons, though technically both Cons and Nil are concrete implementations.

Here's the problem though: we want to be able to pattern-match on an instance of List to get back the contents. As things stand, that pattern matching would require the following syntax:

def sum(xs: List[Int]): Int = xs match {
  case Cons(hd, tl) => hd + sum(tl)
  case Nil => 0
}

This is a bit ugly though. What we really want is to be able to use the :: operator in our pattern matching just the same as we use it when constructing the list originally. This is why the Cons class is named ::.

By defining a case class of two parameters, we're basically telling Scala that we want it to allow us to use that case class as an infix extractor in pattern matching. The trailing colon makes that extractor right-associative, giving us the expected syntax:

sealed trait List[+A]

case class ::[+A](head: A, tail: List[A]) extends List[A]
case object Nil extends List[Nothing]

def sum(xs: List[Int]): Int = xs match {
  case hd :: tl => hd + sum(tl)
  case Nil => 0
}

This is why any instance of List that has contents will be an instance of class ::, since that is the non-empty implementation of List.

Answer 2

This is to work with pattern matching. You have something called an Infix Operator Patterns where pattern p op q is equivalent to the constructor or extractor pattern op(p, q).

So the case class :: defines the constructor ::(head, tail). That allows you to match like this:

list match {
  case ::(head, tail) =>
}

But with the infix operator pattern, you can write the more familiar syntax:

list match {
  case head :: tail =>
}

Note that a stackoverflow search on "[scala] infix operator pattern" returns similar questions and additional use cases of the pattern.