How does Scala Cons pattern matching determine the head and the tail of a List?

Question

How is the head and tail determined in the following statement:

 val head::tail = List(1,2,3,4);
 //head: 1  tail: List(2,3,4)

Shouldn't there be some piece of code which extracts the first element as head and returns the tail as a new List. I've been combing through the Scala standard library code and I can't find/understand how/where this is done.

Adjust

blog.lunatech.com/2011/11/25/scala-list-extractor-demystified good explanation how it works – Duaneduarchy

@eugene-zhulenev, thank you for the link. This was spot on. The Cons case class automatically provides the means to both construct a List instance and deconstruct it into a head and a tail. – Adjust

@Adjust the link from eugene zhulenev is broken. What do you think about my answer below? – Hydrostatics

Answer 1

The Scala construct involved here is the Extractor. The symbol :: is nothing but a case class in Scala, where an an unapply method exists on its companion object to make the extraction magic happen. Here is a good in-depth tutorial on extractors. But here's the summary:

Whenever you want to "unpack" the contents of a class, either for variable binding or as a part of pattern matching, the compiler looks for the method unapply on whatever symbol is on the left hand side of the expression. This may be an object, a case class companion object (like ::, in your question), or an instance with an unapply. The argument to unapply is the incoming type to unpack, and the return type is an Option of what has been declared as the expected structure and types. In pattern matching a None indicates a match was not found. In variable binding a MatchError is thrown if None is the result.

A good way of thinking about unapply is that it is the inverse of apply. Where unapply the receiver of function-call syntax, unapply is the receiver of extractor calls.

To illustrate this further, let's define a simple case class:

case class Cat(name: String, age: Int)

Because it's a case class, we get automatically generated apply and unapply methods on the companion object, which roughly look like this:

object Cat {
  // compiler generated...
  def apply(name: String, age: Int) = new Cat(name, age)    
  def unapply(aCat: Cat): Option[(String, Int)] = Some((aCat.name, aCat.age))
}

When you create a Cat via the companion object, apply is called. When you unpack the constituent parts of a Cat, unapply is called:

val mycat = Cat("freddy", 3) // `apply` called here
...
val Cat(name, age) = mycat   // `unapply` called here
...
val animal: AnyRef = mycat
val info = animal match {
  case Cat(name, age) => "My pet " + name // `unapply` called here
  case _ => "Not my pet"
}
// info: String = My pet freddy

Because unapply returns an Option, we have a lot of power to write extractors that handle more interesting cases, for instance, testing whether the incoming type conforms to some criteria before extracting values. For example, let's say we want to get the name of cats that are "old". One might do this:

object OldCatName {
  def unapply(aCat: Cat) = if (aCat.age >= 10) Some(aCat.name) else None
}

Usage would be the same as a generated unapply:

val yourcat = Cat("betty", 12)
...
val OldCatName(name1) = yourcat
// name1: String = "betty"
val OldCatName(name2) = mycat
// scala.MatchError: Cat(freddy,3) (of class Cat) 

MatchErrors aren't a nice thing to allow, so let's use pattern matching:

val conditions = Seq(mycat, yourcat) map { 
  case OldCatName(oldie) => s"$oldie is old"
  case Cat(name, age) => s"At age $age $name is not old"
}
// conditions: Seq[String] = List(At age 3 freddy is not old, betty is old)

The one extra bit of magic involved with the unapply method for :: is that some syntactic sugar allows val ::(head, tail) = ... to be written val head :: tail = ... instead.

Hydrostatics