This is a short exploration of variances, with some hopefully easy-to-grok examples to elucidate some intuition, especially on the various types of variances that exist¹. While researching this post, I also came across some interesting Scala variances, which I will show here².

#Substitution

In a sense, subtypes are about substitution, or replacing one subtype where another one is expected. Given a simple hierarchy like this:

class Animal(name: String) {
  def getName: String = name
}
 
class Dog(name: String, barkSound: String) extends Animal(name) {
  def getBarkSound: String = barkSound
}

If Dog is a subtype of Animal, then wherever an Animal is expected, a Dog can be provided. This is formalized as Liskov’s Substitution Principle, also known as the L in SOLID.

In Scala, the ability to subtype comes with the ability to annotate type parameters with variances. Variances (along with type bounds) are useful in specifying additional information about the relationships between types and the type constructors they are used in.

#Covariance

If Dog subtypes Animal, then it stands to reason that a list of Dogs also subtypes a list of Animals. That is to say, the List type constructor is covariant in its one type parameter A, as represented in Scala below with the + syntax:

trait List[+A]

The Option type constructor is also covariant in its type parameter:

trait Option[+A]
case class Some[+A](get: A) extends Option[A]
case object None extends Option[Nothing]

So Option[Dog] is a subtype of Option[Animal].

Most of the standard collection type constructors used to express multiples of things (Stream, Vector, IndexedSeq, for example) are also covariant, except maps and sets.

Maps are covariant only in its second parameter, which represents the “value”:

trait Map[K, +V]

and sets are invariant in its type parameter:

trait Set[A]

Sets are invariant in its type parameter because its internal implementation uses maps with dummy values. But why are maps invariant in the first parameter?

To find the answer, we must first see how the variances of functions work.

#Contravariance

Functions have types too. Function1[A, B] represents a function that takes in one parameter of type A and returns something of type B. Function2[A, B, C] represents a function that takes in two parameters of type A and B respectively, and returns something of type C. And so on.

So, is Function1 covariant in both A and B?

It turns out that Function1 is indeed covariant in B. However, it is contravariant in A[^function], or expressed in code:

trait Function1[-A, +B]
// and by extension
trait Function2[-A, -B, +C]

What does contravariance mean, and why is it the way it is?

To answer the first question, for some type constructor F which is contravariant in its type parameter as denoted with the - syntax:

trait F[-A]

if Y is a subtype of X, then F[X] is a subtype of F[Y]. Contravariance is, as you’ll note, the opposite of covariance.

For the second question, let’s first try to motivate some intuition using some contrived examples.

class Publication(body: String) {
  def content: String = body
}
 
class Book(body: String) extends Publication(body)
 
class Animal(name: String) {
  def getName: String = name
}
 
class Dog(name: String, barkSound: String) extends Animal(name) {
  def getBarkSound: String = barkSound
}
 
class Poodle(name: String, colour: String) extends Dog(name, "wof") {
  def getColour: String = colour
}
 
class Husky(name: String, size: Int) extends Dog(name, "GRRR") {
  def getSize: Int = size
}

We define two class hierarchies here, one for publications and books, and one for animals, dogs, and poodles.

Then, we define a function called print, which takes in a function, invokes it, and prints the contents of the result:

def print(fn: Dog => Publication) = (d: Dog) => {
  println(fn(d).content)
}

We can start by defining exactly such a function:

val andy: Dog = new Dog("andy", "gruff")
def dogPublication(d: Dog) = new Publication(s"book on ${d.getBarkSound}")
 

dogPublication returns a new publication on dogs, based on the sound of its bark. If we pass dogPublication to print, we get book on gruff, as expected:

print(dogPublication)(andy) // prints "book on gruff"

So far, so good.

Let’s say we go with our intuition that since Poodle subtypes Dog, and Book subtypes Publication, we should also be able to pass in a function of Poodle => Book. So we define one:

val jane: Poodle = new Poodle("jane", "brown")
def poodleBook(p: Poodle) = new Book(s"book on ${p.getColour}")

This time, poodleBook returns a new book on poodles, based on the colour of the poodle passed in. This is all perfectly okay, since we’re only dealing with poodles here.

We’ll then swap it out:

print(poodleBook)(jane)

If you try to compile that, you get:

error: type mismatch;
 found   : Poodle => Book
 required: Dog => Publication
  print(poodleBook)(jane)
        ^

Why did this happen? If you look at poodleBook closely, you’ll see that it’s using getColour, a method that only Poodle has. However, print is only ever going to pass in Dogs to fn, and we have no idea if d will be a Poodle, or a Husky³.

Let’s see what happens if we go the other way instead, defining a function of Animal => Book:

def animalBook(a: Animal) = new Book(s"book on ${a.getName}")

And if we run that:

print(animalBook)(jane) // prints "book on jane"

We’ll see that this works. This is because animalBook makes use of getName, a method that all Animals have, including Dogs and Poodles. So even if print is only passing in Dog to fn, we are safe using animalBook because it only uses getName, and all Dogs have getName, regardless of which subtype it is.

More generally, function types are contravariant in their input types and covariant in their output types. As shown above, this happens because if we substitute⁴ one function for another one, we need to make sure that the replacement requires less than the original function does, and ouputs more than the original function does.

Recall that supertypes can do less than their subtypes can (Animal has one method, Poodle has three), so for a function X to be considered a subtype of Y, its input types must be supertypes of the Y’s input types.

#Map Key Invariance

With that out of the way, we can finally answer the question of why maps are invariant in the first type parameter.

Since maps have a get method (amongst other methods, of course), it might seem straightforward that maps should be contravariant in the first type parameter, since get is a function that takes a parameter of type K:

trait Map[K, +V] {
  def get(key: K): Option[V]
}

However, maps also have methods like keys, which returns an Iterable[K].

 
trait Map[K, +V] {
  def get(key: K): Option[V]
  def keys: Iterable[K]
}

Since the output is covariant with K, this means that K can neither be contravariant nor covariant. See the definitive reply on this here.

#Footnotes