This is an attempt to fully understand how to use scala's and similar languages' generics better through using variance techniques. Everyone knows the principle of Liskov's Substitution prinsiple as seen in SO*L*ID principles. So these techniques are not only for functional programming languages because Scala is a decent object oriented programming language, too.

Subtyping and Variance

Barbara Liskov's Substitution prinsiple (LSP): Given A <: B, anything one can to do with a value of B, one should also be able to do with a value of type A.

This subject is heavily related to these and their combined usages:

• Subtyping
• Generics

Basic definitions on scala:

S <: IntSet means S is any subtype of (including) IntSet S >: T means S is a super type of (including) T

1def assertAllPos[S <: IntSet](r: S): S = ...

In this code, the function takes a parameter r whose type is a subtype of IntSet and returns a subtype of IntSet again.

We could say

1[S >: NonEmpty]

or even

1[S >: NonEmpty <: IntSet]

So the hard question would be, given NonEmpty <: IntSet, is also List[NonEmpty] <: List[IntSet]?

Variance

Covariant

When we think about it, the above statement will be true and called covariant because the relationship varies with the type parameter.

In c# (or java) one could have done

1NonEmpty[] a = new NonEmpty[] { new NonEmpty() };
2IntSet[] b = a;
3b[0] = new Empty();
4NonEmpty s = a[0];

But all we could have this runtime error:

1System.ArrayTypeMismatchException: Attempted to access an element as a type incompatible with the array. (line 4)

Because c# arrays are covariant and mutable we got this error. Fortunately generic collections in c# are invariant so you'll have a compile-time check. Also scala's mutable arrays are not covariant unlike java and c# arrays.

http://stackoverflow.com/a/2033921/2049893

Variance (cont.)

Knowing the above, now we can go further: C[T] is a parameterised type and A, B are types such that A <: B

• Covariant if C[A] <: C[B]
• Contravariant if C[A] >: C[B]
• Invariant if neither C[A] nor C[B] is a subtype of the other

Scala lets you define variance like:

1class C[+A] { ... } // C is covariant
2class C[-A] { ... } // C is contravariant
3class C[A] { ... }  // C is nonvariant

If we have two function types (NonEmpty <: IntSet and Empty <: IntSet):

1type A = IntSet => NonEmpty
2type B = NonEmpty => IntSet
3
4A -> NonEmpty,Empty => NonEmpty
5B -> NonEmpty       => NonEmpty,Empty

If one pass NonEmpty to the function A, it returns NonEmpty and it is still an IntSet. But you can't do the same to the function B as you can't pass Empty to function B and it can return Empty. So it is A <: B.

To generalise, given A2 <: A1 and B1 <: B2:

1A1 => B1 <: A2 => B2

So functions are contravariant in their argument types, and covariant in their result type.

1trait Function1[-T, +U] {
2    def apply(x: T): U
3}

This is a built-in function defined in scala.

So the rules are:

• covariant type parameters can only appear in method results.
• contravariant type parameters can only appear in method parameters.
• invariant type parameters can appear anywhere.

But why is Nil < List[T]:

Nothing is a subtype of every other type (including Null); there exist no instances of this type. Although type Nothing is uninhabited, it is nevertheless useful in several ways. For instance, the Scala library defines a value scala.collection.immutable.Nil of type List[Nothing]. Because lists are covariant in Scala, this makes scala.collection.immutable.Nil an instance of List[T], for any element of type T.

Example

Lets see the List example here, which is a basic re-implementation of scala's immutable List:

 1// made List covariant
 2trait List[T] {
 3  def isEmpty: Boolean
 4  def head: T
 5  def tail: List[T]
 6}
 7
 8class Cons[T](val head: T, val tail: List[T]) extends List[T] {
 9  override def isEmpty: Boolean = false
10}
11
12class Nil[T] extends List[T] {
13  override def isEmpty: Boolean = true
14
15  override def head: Nothing = throw new NoSuchElementException("Nil.head")
16
17  override def tail: Nothing = throw new NoSuchElementException("Nil.tail")
18}

And these additional types:

 1abstract class IntSet {
 2  def incl(x: Int): IntSet
 3}
 4
 5object Empty extends IntSet {
 6  override def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty)
 7}
 8
 9class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
10  override def incl(x: Int): IntSet = {
11    if(x < elem)
12      new NonEmpty(elem, left.incl(x), right)
13    else if(x > elem)
14      new NonEmpty(elem, left, right.incl(x))
15    else
16      this
17  }
18}

First of all, I want to change type Nil from class to object because we don't need to instantiate it. But then we lose generic parameter so we need to change List[T] to List[Nothing] because it is subtype of every other types.

Now in this line new Cons[T](elem, Nil) we get an error:

1Error:(28, 57) type mismatch;
2 found   : A$A0.this.Nil.type
3 required: A$A0.this.List[T]
4Note: Nothing <: T (and A$A0.this.Nil.type <: A$A0.this.List[Nothing]), but trait List is invariant in type T.
5You may wish to define T as +T instead. (SLS 4.5)
6def singleton[T](elem: T): List[T] = new Cons[T](elem, Nil)

As the error message explains: the type T in List we defined is invariant and that means List[Nothing] is not a subtype of List[T], so let's change definition of List to List[+T] covariant. Now everything compiles as expected. The actual implementation has this covariant definition, too.

Bounds

We can define type bounds in our generic types or functions. But why do we need them? Let's see an example: Adding a prepend method to the List type.

1def prepend(elem: T): List[T] = new Cons(elem, this)

Because we can use both Empty and NonEmpty as type T, this will violate LSP, will give a compile-time error:

1Error:(8, 16) covariant type T occurs in contravariant position in type T of value elem
2  def prepend(elem: T): List[T] = new Cons(elem, this)
3              ^

If we have defined our type as covariant, we also need to use parameters as contravariant. This means we need a type that have lower bound of T. We need to change our function like this:

1def prepend[U >: T](elem: U): List[U] = new Cons(elem, this)
2
3def f(xs: List[NonEmpty], x: Empty) = xs.prepend(x)

Function f's return type will be inferred as List[IntSet] automatically On our function, U will be an Empty, T will be NonEmpty and they are also IntSets.