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

Posted on:October 6, 2020

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 exist1. While researching this post, I also came across some interesting Scala variances, which I will show here2.

# #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 `Dog`s also subtypes a list of `Animal`s. 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 `Dog`s to `fn`, and we have no idea if `d` will be a `Poodle`, or a `Husky`3.

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 `Animal`s have, including `Dog`s and `Poodle`s. So even if `print` is only passing in `Dog` to `fn`, we are safe using `animalBook` because it only uses `getName`, and all `Dog`s 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 substitute4 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

## #Footnotes

1. I will not cover bivariance here.

2. I apologize in advance for any sloppy Scala code — these examples are purely meant to be educational.

3. I like huskies more than poodles, for the record.

4. Recall Liskov’s Substitution Principle above.