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 Dogs also sub­types a list of Animals. 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 A5, 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 Dogs to fn, and we have no idea if d will be a Poodle, or a Husky3.

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 Animals have, includ­ing Dogs and Poodles. So even if print is only pass­ing in Dog to fn, we are safe using animalBook because it only uses getName, and all Dogs 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.