Scala match decomposition on infix operator

Question

I'm trying to understand the implementation of Lists in Scala. In particular I'm trying to get my head around how you can write match expressions using an infix operator, for example:

a match {
  case Nil => "An empty list"
  case x :: Nil => "A list without a tail"
  case x :: xs => "A list with a tail"
}

How is the match expression allowed to be x :: xs rather than List(x, xs)?

Answer 1

Jay Conrad's answer is almost right. The important thing is that somewhere there is an object named :: which implements the unapply method, returning type Option[(A, List[A])]. Thusly:

object :: {
  def unapply[A](ls: List[A]): Option[(A, A)] = {
    if (ls.empty) None
    else Some((ls.head, ls.tail))
  }
}

// case objects get unapply for free
case object Nil extends List[Nothing]

In the case of :: and List, this object happens to come out of the fact that :: is a case class which extends the List trait. However, as the above example shows, it doesn't have to be a case class at all.

Answer 2

I believe :: is actually a class (which is a subclass of List), so saying x :: xs is mostly equivalent to List(x, xs).

You can do this with other case classes that have operator names. For instance:

case class %%%(x: Int, y: Int)

a match {
  case x %%% y => x + y
}

Answer 3

How is the match expression allowed to be x :: xs rather than List(x, xs)?

To answer this question:

When seen as a pattern, an infix operation such as p op q is equivalent to op(p, q). That is, the infix operator op is treated as a constructor pattern.

(Programming in Scala, 1st ed., p. 331)

See also scala case classes questions