How does the Scala type system know that cons + Nil is exhaustive?

Question

I just wrote this function, wondering what would happen if I omitted the Nil case, and noticed that scalac gives me a warning:

def printList[String](list: List[String]) {
    list match {
        case head :: tail => {
            println(head)
            printList(tail)
        }
        //case Nil => println("Done")
    }
}

Warning: match may not be exhaustive. It would fail on the following input: Nil

I'm having trouble pinning down exactly what's going on here. I get the general idea of pattern matching on a recursive data type until you exhaust the cases, but it's not clear to me how that maps to the Scala type system. Specifically, I'm looking at the source code of the Scala standard library and wondering:

1. Where exactly in the code is Scala getting the idea that a base case is required to complete a match statement for an instance of the List class? One could certainly imagine an algebraic data type that "just keeps going" with no base case.
2. Where exactly in the code is scala.collection.immutable.Nil in particular designated as the base case for the List class?

Answer 1

It's actually not as complicated as you think. List is a sealed abstract class with exactly two implementations, Nil and :: (yes that is the name of the class). The important part here is the sealed modifier. This simply enforces that any class that implements List must be in the same source file as List itself.

The importance of sealed is that now the compiler knows for sure every possible implementor of List, so if you pattern match against a list, the compiler can figure out if your pattern matching block is exhaustive.

The one last thing to realise is that there is some syntactic sugar going on with ::. Normally if you have some case class:

case class Foo(a: String, b: Int)

you would match it as such

x match {
  case Foo(a, b) => //...
}

However when you have a case class with exactly two members, you can also write it as such:

x match {
  case a Foo b => //...
}

So in your pattern matching statement, you're really doing:

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

so really all you're doing is checking if list is an instance of ::. Thus the compiler can see that you're never checking if list is an instance of Nil and warns you.