# Type Variances (or, Why Maps Are Invariant in Its Key Type)

October 06, 2020

This is a short explo­ration of vari­ances, with some hope­ful­ly easy-to-grok exam­ples to elu­ci­date some intu­ition, espe­cial­ly on the var­i­ous types of vari­ances that exist1. While research­ing this post, I also came across some inter­est­ing Scala vari­ances, which I will show here2.

# Sub­sti­tu­tion

In a sense, sub­types are about sub­sti­tu­tion, or replac­ing one sub­type where anoth­er one is expect­ed. Given a simple hier­ar­chy 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 sub­type of `Animal`, then wher­ev­er an `Animal` is expect­ed, a `Dog` can be pro­vid­ed. This is for­mal­ized as Liskov’s Sub­sti­tu­tion Prin­ci­ple, also known as the L in SOLID.

In Scala, the abil­i­ty to sub­type comes with the abil­i­ty to anno­tate type para­me­ters with vari­ances. Vari­ances (along with type bounds) are useful in spec­i­fy­ing addi­tion­al infor­ma­tion about the rela­tion­ships between types and the type con­struc­tors they are used in.

# Covari­ance

If `Dog` sub­types `Animal`, then it stands to reason that a list of `Dog`s also sub­types a list of `Animal`s. That is to say, the `List` type con­struc­tor is covari­ant in its one type para­me­ter `A`, as rep­re­sent­ed in Scala below with the `+` syntax:

``trait List[+A]``

The `Option` type con­struc­tor is also covari­ant in its type para­me­ter:

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

So `Option[Dog]` is a sub­type of `Option[Animal]`.

Most of the stan­dard col­lec­tion type con­struc­tors used to express mul­ti­ples of things (`Stream`, `Vector`, `IndexedSeq`, for exam­ple) are also covari­ant, except maps and sets.

Maps are covari­ant only in its second para­me­ter, which rep­re­sents the “value”:

``trait Map[K, +V]``

and sets are invari­ant in its type para­me­ter:

``trait Set[A]``

Sets are invari­ant in its type para­me­ter because its inter­nal imple­men­ta­tion uses maps with dummy values. But why are maps invari­ant in the first para­me­ter?

To find the answer, we must first see how the vari­ances of func­tions work.

# Con­travari­ance

Func­tions have types too. `Function1[A, B]` rep­re­sents a func­tion that takes in one para­me­ter of type `A` and returns some­thing of type `B`. `Function2[A, B, C]` rep­re­sents a func­tion that takes in two para­me­ters of type `A` and `B` respec­tive­ly, and returns some­thing of type `C`. And so on.

So, is `Function1` covari­ant in both `A` and `B`?

It turns out that `Function1` is indeed covari­ant in `B`. How­ev­er, it is con­travari­ant in `A`5, or expressed in code:

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

What does con­travari­ance mean, and why is it the way it is?

To answer the first ques­tion, for some type con­struc­tor `F` which is con­travari­ant in its type para­me­ter as denot­ed with the `-` syntax:

``trait F[-A]``

if Y is a sub­type of X, then `F[X]` is a sub­type of `F[Y]`. Con­travari­ance is, as you’ll note, the oppo­site of covari­ance.

For the second ques­tion, let’s first try to moti­vate some intu­ition using some con­trived exam­ples.

``````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 hier­ar­chies here, one for pub­li­ca­tions and books, and one for ani­mals, dogs, and poo­dles.

Then, we define a func­tion called `print`, which takes in a func­tion, invokes it, and prints the con­tents of the result:

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

We can start by defin­ing exact­ly such a func­tion:

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

`dogPublication` returns a new pub­li­ca­tion on dogs, based on the sound of its bark. If we pass `dogPublication` to `print`, we get `book on gruff`, as expect­ed:

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

So far, so good.

Let’s say we go with our intu­ition that since `Poodle` sub­types `Dog`, and `Book` sub­types `Publication`, we should also be able to pass in a func­tion 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 poo­dles, based on the colour of the poodle passed in. This is all per­fect­ly okay, since we’re only deal­ing with poo­dles here.

We’ll then swap it out:

``print(poodleBook)(jane)``

If you try to com­pile that, you get:

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

Why did this happen? If you look at `poodleBook` close­ly, you’ll see that it’s using `getColour`, a method that only `Poodle` has. How­ev­er, `print` is only ever going to pass in `Dog`s to `fn`, and we have no idea if `d` will be a `Poodle`, or a `Husky`3.

Let’s see what hap­pens if we go the other way instead, defin­ing a func­tion 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 `Animal`s have, includ­ing `Dog`s and `Poodle`s. So even if `print` is only pass­ing in `Dog` to `fn`, we are safe using `animalBook` because it only uses `getName`, and all `Dog`s have `getName`, regard­less of which sub­type it is.

More gen­er­al­ly, func­tion types are con­travari­ant in their input types and covari­ant in their output types. As shown above, this hap­pens because if we sub­sti­tute4 one func­tion for anoth­er one, we need to make sure that the replace­ment requires less than the orig­i­nal func­tion does, and ouputs more than the orig­i­nal func­tion does.

Recall that super­types can do less than their sub­types can (`Animal` has one method, `Poodle` has three), so for a func­tion `X` to be con­sid­ered a sub­type of `Y`, its input types must be super­types of the `Y`’s input types.

# Map Key Invari­ance

With that out of the way, we can final­ly answer the ques­tion of why maps are invari­ant in the first type para­me­ter.

Since maps have a `get` method (amongst other meth­ods, of course), it might seem straight­for­ward that maps should be con­travari­ant in the first type para­me­ter, since `get` is a func­tion that takes a para­me­ter of type `K`:

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

How­ev­er, maps also have meth­ods 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 covari­ant with `K`, this means that `K` can nei­ther be con­travari­ant nor covari­ant. See the defin­i­tive reply on this here.

# Foot­notes

1. I will not cover bivari­ance here.

2. I apol­o­gize in advance for any sloppy Scala code — these exam­ples are purely meant to be edu­ca­tion­al.

3. I like huskies more than poo­dles, for the record.

4. Recall Liskov’s Sub­sti­tu­tion Prin­ci­ple above.