Demystifying Variance Positions in Scala

Introduction

Variance in Scala is one of the most powerful concepts of its type system. It’s simple in theory, but it can cause massive headaches when we think we got the hang of writing abstract, generic code. In this article, we’ll take a careful and structured look at one of the most cryptic compiler errors you’ll ever see:

covariant type T occurs in contravariant position in type T of value myArg

We won’t need a particular project setup for this article - a plain Scala/sbt project will do.

Prerequisites

This article will assume you’re familiar with generics (either in Java, Scala or some other statically typed language).

Beyond the capability of the Java generics, Scala also has the concept of variance, which is a way of transferring the subtype relationship from the type arguments to the generic type.

This sounds quite complicated until we bring it back to real life. Imagine we’re implementing a generic collection which we’ll call MyList[T]. If we have a small class hierarchy — -e.g. the classical example with Animals and then Cats and Dogs which extend Animals — then it makes sense to ask the following question:

If Dogs are also Animals, then is a list of Dogs also a list of Animals?

For a list, the answer is yes. However, this answer doesn’t make sense for every type.

The Variance Question

To put it another way, if we wanted to write a new Thing[T] generic type in our code base, the following question is important:

If A is a subtype of B, then should Thing[A] be a subtype of Thing[B]?

This is the variance question.

If our Thing is a collection, such as a list, the answer is yes: if Dogs are Animals, then a collection of Dogs is also a collection of Animals. So from a substitution perspective, we could assign a collection of Dogs to a collection of Animals:

val dogs: MyList[Animal] = new MyList[Dog]

We say that MyList is covariant in its type argument [T], and we mark it with a small + sign in the class declaration: class MyList[+T]

But that’s not the only possibility. We can also answer “no”, i.e. Thing[A] and Thing[B] have no subtype relationship, i.e. we can’t assign one to a value bearing the other type. In this case, we’d call Thing invariant in its type argument [T], and we leave the type argument T as it is in the class declaration, i.e. class Thing[T]

There’s still one more possible answer: “hell no, it’s backwards!”. In other words, if A is a subtype of B, then Thing[B] is a subtype of Thing[A]. This is called contravariant, and we mark it with a - sign at the class declaration. For the Animals use case, a good contravariant example would be a Vet:

class Vet[-T]

val lassiesVet: Vet[Dog] = new Vet[Animal]

A Vet[Animal] is a proper replacement for a Vet[Dog], because a Vet can treat any Animal, and so she/he can treat a Dog too.

If you want to keep a good rule of thumb on how to pick variance for your new generic type, it’s this:

The Variance Positions Problem

Now that we’ve found that a collection should be covariant, we get to work and write our own list, because of course we can:

abstract class MyList[+T] {
  def head: T
  def tail: MyList[T]
  def add(elem: T): MyList[T]
}

We start from the very basics. But before we even write a proper subtype for MyList, we hit a wall:

covariant type T occurs in contravariant position in type T of value elem

Just as we thought we understood variance, here comes the compiler trying to prove we don’t know squat.

We’ll take a careful, structured approach of what this problem means, and then we’ll learn how we can solve it. For the following examples, we’ll use the same example with animals.

class Vet[-T](val favoriteAnimal: T)

val garfield = new Cat
val theVet: Vet[Animal] = new Vet[Animal](garfield)
val lassiesVet: Vet[Dog] = theVet

contravariant type T occurs in covariant position in type T of value favoriteAnimal

val maybeAnimal: MutableSome[Animal] = new MutableSome[Dog](new Dog)
maybeAnimal.contents = new Cat

abstract class MyList[+T] {
  def head: T
  def tail: MyList[T]
  def add(elem: T): MyList[T]
}

val animals: MyList[Animal] = new MyList[Cat]
val moreAnimals = animals.add(new Dog)

class Vet[-T] {
  def heal(animal: T): Boolean = true // implementation unimportant
}

val lassiesVet: Vet[Dog] = new Vet[Animal]
lassiesVet.heal(lassie) // correct; it's a Dog, which is also an Animal; Vet[Animal] can heal any Animal
lassiesVet.heal(garfield) // legitimate error: Lassie's vet heals Dogs, so Cats aren't allowed

abstract class Vet[-T] {
  def rescueAnimal(): T
}

val vet: Vet[Animal] = new Vet[Animal] {
  override def rescueAnimal(): Animal = new Cat
}

val lassiesVet: Vet[Dog] = vet // OK because it's a Vet[Animal]
val rescuedDog: Dog = vet.rescueAnimal // what's up dawg, I'm a Cat

How to Solve the Variance Positions Problem

We proved that a covariant list cannot have an add(elem: T) method because it breaks type guarantees. However, does that forbid us from ever adding an element to a list?!

Hell, no.

Let’s take this back to first principles. We said that we can’t add an add(elem: T) method to a list, because otherwise we could write

val animals: MyList[Animal] = new MyList[Dog]
val moreAnimals = animals.add(new Cat)

Go back to real life: if we had 3 dogs and a cat, what would the group of 4 be called?

Animals. The most specific type that describes all four.

What if our add(elem: T): MyList[T] received an argument of a different type and returned a result of a different type? Allow me to make a suggestion:

def add[S >: T](elem: S): MyList[S]

In other words, if we happen to add an element of a different type than the original list, we’ll let the compiler infer the lowest type S which describes both the element being added AND the existing elements of the list. As a result, we’ll obtain a MyList[S]. In our cats vs dogs example, if we add a cat to a list of dogs, we’ll obtain a list of animals. If we add a flower to it, we’ll obtain a list of life forms. If we add a number, we’ll obtain a list of Any. You get the idea.

This is how we solve the cryptic “covariant type T occurs in contravariant position”:

abstract class MyList[+T] {
  def add[S >: T](elem: S): MyList[S]
}

Similarly, we can solve the opposite “contravariant type occurs in covariant position” with the opposite type bound:

abstract class Vet[-T] {
  def rescueAnimal[S <: T](): S
}

Assuming we can actually implement this method in such general terms, the compiler would be happy: we can force the Vet to return an instance of a particular type:

val lassiesVet: Vet[Dog] = new Vet[Animal]
val rescuedDog: Dog = vet.rescueAnimal[Dog] // type checking passes now

Conclusion

This is one of the hardest parts of the Scala type system, even though it starts from such an innocent question (should lists of dogs be lists of animals). If you’re curious, the advanced Scala course contains what you’ve just learned (and lots more on Scala’s type system) with some practice exercises.

This article was pretty dense, and we learned quite a bit:

• The variance question: if A extends B, should Thing[A] be a subtype of Thing[B]?
• Variance possibilities as answers to the variance question: covariant (yes), invariant (no), contravariant (hell no, backwards)
• Types val fields are in covariant position
• Types of var fields are in covariant AND contravariant position
• Types of method arguments are in contravariant position
• Method return types are in covariant position
• We solve the “covariant type occurs in contravariant position” by “widening”: we add a type argument [S >: T] and change the argument type to S
• We solve the “contravariant type occurs in covariant position” by “narrowing”: we add a type argument [S <: T] and change the method return type to S