Note: Lists (i.e., functional stacks) and variance

In Scala, a list (or stack) data structure will in fact typically be defined as follows:

enum Stack[+A]:
  case Empty extends Stack[Nothing]
  case Cons(head: A, tail: Stack[A])

Notice two important changes from the definition we saw before:

• The Empty case no longer has an empty parameter list. Instead, it uses an extends clause.

Since Empty is now a plain object (called a singleton) and no longer a data constructor instantiated with an empty argument list, the Scala compiler no longer knows what its relationship with the Stack type constructor should be. For Cons, it infers a Cons[A] type which extends the Stack[A] type. But objects cannot have type parameters, and Scala 3 does not know what Stack[?] the Empty object should extend. So we specify explicitly that it extends Stack[Nothing].

• The type parameter ‘A’ in Stack is defined as covariant, indicated with the ‘+’ sign.

Covariance means that there is a subtyping relationship between stack types whose type arguments have a subtyping relationship, in the same direction. In other words, if A is a subtype of B, then Stack[A] is a subtype of Stack[B].

Since Nothing is the bottom of the Scala subtyping lattice, we have the useful relationship that, for any T, then Empty is a subtype of Stack[T]. This means we can use the same empty stack object as the root of stacks of arbitrary types! For instance, 1 :: 2 :: Empty and "a" :: "b" :: Empty.

Update: In fact, since a recent version of Scala 3, one can now omit the extends clause and Nothing is inferred:

enum Stack[+A]:
  case Empty
  case Cons(head: A, tail: Stack[A])