Type variance

Type variance is a subject that I’ve long found confusing and counter-intuitive. Attempting to use the semi-mystical [+A] or [-A] type annotations would, more often than not, yield an obscure covariant type A occurs in contravariant position in type A... compilation error.

I’ve finally decided to bite the bullet and make sense of it all. This post is what I came up with after hacking at / reading on type variance until I decided I had it as figured out as I was likely to for the time being.

Type variance

Type variance is in itself a fairly simple concept: classes who process or store values often do not need to know the exact type of these values, or only need them to follow a known set of constraints.

For example, a List doesn’t really need to know what it stores - it’ll behave exactly the same way whether it contains instances of Int or String.

One simple way of writing the List class to reflect this is to have it store instances of AnyRef, but that would be at the cost of type safety: since there is no constraint on the stored elements, there’s nothing to prevent a List from storing instances of both Int and String.

Parametric polymorphism allows you to turn the type of elements contained by List into a parameter, through the following syntax:

// A is the type manipulated by List.
trait List[A] {
  // A can be referenced in List's body.
  def append(a: A): List[A]
}

This declares a List trait that contains elements of type A, to be defined at declaration time. There’s what I feel is an unfortunate wealth of vocabulary to describe this:

Using the previous declaration of List, it becomes possible to write code that is both generic and type safe:

val li: List[Int] = new List[Int] { override def append(i: Int) = this }

This works fine: 1 is an Int and thus a legal parameter for append.

li.append(1)

This, however, fails: passing a String value to append is not legal.

li.append("foobar")

Note that you might sometimes want to have a list of elements of any type - this is easily achieved by declaring it as List[AnyRef].

Type variance describes how the relation between instances of List vary with the value of their type parameter. I’ll explore these in the rest of this post, using the following traditionnal class hierarchy for illustration:

// A Mammal has a name.
class Mammal(val name: String)

// A Dog is a Mammal that can bark.
class Dog(name: String) extends Mammal(name) {
  def bark(): Unit = println("bark!")
}

// A Cat is a Mammal that purrs.
class Cat(name: String) extends Mammal(name) {
  def purr(): Unit = println("purrrr")
}

Invariance

By default, generic classes are invariant on their parameter(s): whatever the relation between A and B, there won’t be any particular relationship between List[A] and List[B] - B could, for example, be a subclass of A, but this would have no bearing on how List[B] relates to List[A].

List is a nice example in that it’s a well known structure that’s easy to reason about, but it’s a bit cumbersome when I wish to write actual code. Let’s declare a simple Wrapper class, invariant in A:

case class Wrapper[A](val a: A) {
  // Retrieves the wrapped value.
  def apply() = a
}

Since Wrapper is invariant on its parameter, there is no relation between Wrapper[Dog] and Wrapper[Mammal].

This does not compile: a Wrapper[Mammal] is not a value of type Wrapper[Dog].

val wd: Wrapper[Dog] = Wrapper(new Mammal("Flipper"))

This does not either: a Wrapper[Dog] is not a value of type Wrapper[Mammal].

val wm: Wrapper[Mammal] = Wrapper[Dog](new Dog("Lassie"))

That last one is a bit of a shame, though: since a Dog is a Mammal, surely a Wrapper[Dog] should be a Wrapper[Mammal] as well? Which smoothly leads us into our next section, covariance.

Covariance

Saying that a class C is covariant on its parameter is saying that if A extends B, then C[A] extends C[B].

In Scala, making a class covariant on its parameter is achieved with the + modifier, as in the following example:

case class Wrapper[+A](val a: A) {
  def apply(): A = a
}

With Wrapper thus modified, our previous example works as expected.

This still does not compile: Wrapper[Mammal] is not an instance of Wrapper[Dog].

val wd: Wrapper[Dog] = Wrapper(new Mammal("Flipper"))

This, however, now compiles: Wrapper is covariant on its type parameter, which makes a Wrapper[Dog] a value of type Wrapper[Mammal].

val wm: Wrapper[Mammal] = Wrapper[Dog](new Dog("Lassie"))

Contravariance

Contravariance is the exact opposite of covariance: saying that a class C is contravariant on its parameter is saying that if A extends B, then C[B] extends C[A].

In scala, making a class contravariant on its parameter is achieved with the - modifier, as in the following example:

trait Printer[-A] {
  // Prints its argument.
  def apply(a: A): Unit
}

This is a bit counter intuitive, but makes sense in the case of classes used to process rather than store others:

// Note how this calls a method defined in Dog but not in Mammal.
class DogPrinter extends Printer[Dog] {
  override def apply(a: Dog): Unit = {
    println(a)
    a.bark()
  }
}

// Since Printer is contravariant, an instance of MammalPrinter is a valid instance of Printer[Dog].
class MammalPrinter extends Printer[Mammal] {
  override def apply(a: Mammal): Unit = {
    println(a)
  }
}

Since a Printer[Mammal] is a valid value of type Printer[Dog], the following is fine:

// Compiles: a Printer[Mammal] is a valid Printer[Dog].
val wd: Printer[Dog] = new MammalPrinter()

On the other hand, a Printer[Dog] is not a valid Printer[Mammal], and the following will fail to compile:

val wm: Printer[Mammal] = new DogPrinter()

If unsure why, consider what happens when DogPrinter calls the bark() method on an instance of Mammal.

Function variance

Before explaining the compilation errors mentionned in the introduction of this post, we must take a closer look at functions and how they vary on their parameters and return types.

In Scala, functions are instances. A unary function, for example, is an instance of Function1[-T, +R], where T is the type of the function’s parameter and R that of its return value.

It’s critical to understand why Function1 is contravariant on its parameter type and covariant on its return type: most of the complexity of type variance comes from that simple fact.

Parameter type

The Printer trait we defined previously fulfills all the requirements of a unary function. We can in fact have it extend Function1[A, Unit] without changing anything else in our previous code:

trait Printer[-A] extends Function1[A, Unit] {
  def apply(a: A): Unit
}

It wouldn’t be possible for Printer to be covariant on A: it would mean that a Printer[Dog] would be a Printer[Mammal], which would allow us to apply Dog specific code to a Mammal - say, call the bark method on an instance of Cat.

This is a general rule: functions are always contravariant on their parameter types.

Return type

Just like Printer fulfilled the contract of a Function1[A, Unit], Wrapper fulfills that of a Function0[A]:

case class Wrapper[+A](val a: A) extends Function0[A] {
  override def apply(): A = a
}

Wrapper could not possibly be contravariant on A: it would mean that a Wrapper[Mammal] would be a valid Wrapper[Dog], which would mean that a valid Wrapper[Dog] could return instances of Cat.

Just as before, this is a general rule: functions are always covariant on their return values.

Explanation of the compilation errors

Covariant in contravariant position

We now have all the necessary keys to understand the dreaded covariant type A occurs in contravariant position in type A... error message.

Let’s first modify our Wrapper class to cause the issue:

case class Wrapper[+A](val a: A) {
  def apply(): A = a

  // This method will cause a compilation error message.
  def set(va: A): Wrapper[A] = Wrapper(va)
}

Armed with our newfound type variance knowledge, this isn’t actually so hard to understand: Wrapper is covariant on A while set is contravariant on A (its parameter type).

Luckily, Scala provides an easy work around through lower type bounds:

case class Wrapper[+A](val a: A) {
  def apply(): A = a

  // Notice how the signature has changed.
  def set[B >: A](vb: B): Wrapper[B] = Wrapper(vb)
}

The [B >: A] bit is telling Scala that a local type B has been declared, and that B must always be a superclass of A.

With that modification, set is no longer covariant on A, but contravariant on B, where B is an instance of A or something more general.

This is all a bit theoretical, so let’s take a concrete example. Let’s pretend that the Scala compiler accepts the following code:

case class Wrapper[+A](val a: A) {
  def apply(): A = a
  def set(va: A): Wrapper[A] = Wrapper(va)
}

If this were to be considered correct, we’d be able to write the following:

class BorkedWrapper(i: Dog) extends Wrapper[Dog](i) {
  override def set(vd: Dog): Wrapper[Dog] = {
    // Pay attention to the fact that we're calling bark(), that's the important bit.
    vd.bark()
    new BorkedWrapper(vd)
  }
}

// Wrapper is covariant on A, and Dog is a subtype of Mammal: an instance of Wrapper[Dog] is a legal instance of
// Wrapper[Mammal]. The following line is perfectly legal.
val wd: Wrapper[Mammal] = new BorkedWrapper(new Dog("Lassie"))

// A `Cat` is a legal instance of `Mammal`, there's nothing wrong with setting one to a Wrapper[Mammal]
wd.set(new Cat("Duchess"))

Scala just let us write code that calls the bark method of Cat, which is obviously impossible - that’s where the compilation error comes from. If were, however, to use lower type bounds, we’d find we can’t provoque such a scenario anymore:

case class Wrapper[+A](val a: A) {
  def apply(): A = a
  def set[B >: A](vb: B): Wrapper[B] = Wrapper(vb)
}

// This class doesn't compile anymore: the set method doesn't actually overwrite Wrapper's, since they don't share
// parameter types. As an aside, that's as perfect an example of the benefit of explicitely writing override as I'm
// likely to find: not using it here would allow the code to compile, and figuring out that we're actually declaring
// two different set methods might take a while.
class BorkedWrapper(i: Dog) extends Wrapper[Dog](i) {
  override def set(vd: Dog): Wrapper[Dog] = {
    vd.bark()
    new BorkedWrapper(vd)
  }
}

// This doesn't compile either:
// - B doesn't have a bark method
// - new DogWrapper(vb) is not legal, since vb is not necessarily an instance of Dog.
class DogWrapper(d: Dog) extends Wrapper[Dog](d) {
  override def set[B >: Dog](vb: B): Wrapper[B] = {
    vb.bark()
    new DogWrapper(vb)
  }
}

val wd: Wrapper[Dog] = Wrapper(new Dog("Lassie"))

// This is now legal: Mammal is a superclass of Dog, so it can be passed to set.
// Note that the returned value is no longer an instance of Wrapper[Dog] but of Wrapper[Mammal].
val wm: Wrapper[Mammal] = wd.set(new Cat("Duchess"))

Contravariant in covariant position

There is of course a symmetrical issue for contravariance, which can be seen with the following code:

trait Printer[-A] {
   def apply(a: A): A
}

This causes the following compilation error: error: contravariant type A occurs in covariant position in type (a: A)A of method apply.

Now that we have a good understanding of contravariance, covariance and how a function varies, this actually makes sense: Printer is contravariant on A while apply is covariant on it (since A is its return value).

We fix this the same way we did before, with type bounds - although this time we use an upper bound:

trait Printer[-A] {
   def apply[B <: A](b: B): B
}

I’d love to give a concrete example here, but I’ve failed to find a convincing one so far. I’ll update this post if I ever do.

Mutable types and variance

A last note about type variance: contravariance and covariance only work with immutable structures. Mutable ones can be invariant, but they cannot be made anything else.

As a demonstration, let’s try to make Wrapper mutable:

case class Wrapper[+A](private var a: A) {
  def get: A = a

  // This won't work: a is an instance of A and cannot be used to store instances of B, since
  // B is necessarily a superclass of A.
  // The only way for this to work is to force B to be the same as A - which means making
  // Wrapper invariant.
  def set[B >: A](vb: B): Unit = a = vb
}