Description of the four kinds of variance: covariance, contravariance, invariance and bivariance.

variance.md

Variance

The term variance describes how subtyping between higher kinded types is related to subtyping relations of their type arguments.

Higher Kinded Types

A higher kinded type composes type arguments to a new type. I use square bracket notation to define a higher kinded type:

C[T] // The higher kinded type `C` composes type argument `T` to a new type `C[T]`.

The same works with multiple type arguments:

C[T, R] // The higher kinded type `C` composes type arguments `T` and `R` to a new type `C[T, R]`.

Function

Function types are higher kinded types with multiple type arguments. The last type argument defines the return type. All previous type arguments describe the function parameter types.

Function[Number] // () => Number
Function[Void] // () => Void
Function[String, Number] // (String) => Number
Function[Boolean, String, Number] // (Boolean, String) => Number

Higher kinded types can compose higher kinded types:

Function[Array[String], Number] // (Array[String]) => Number
Function[Function[String, Number], Boolean, Void] // ((String) => Number, Boolean) => Void

Array

An array is a list of values of a type:

Array[Number] // list of numbers
Array[String] // list of strings

An array has methods to add and get elements. I define array as

interface Array[T] {
    add(element: T) => void
    get(index: Number) => T
}

Note: I disregard other properties in this definition to keep it simple.

Array[Number] has methods add(element: Number) => void and get(index: Number) => Number. On the other hand, Array[String] has methods add(element: String) => void and get(index: Number) => String.

Subtyping

Given types Animal, Dog and Cat, where Dog is subtype of Animal and where Cat is subtype of Animal, but neither Dog is subtype of Cat nor Cat is subtype of Dog:

  Animal
     ^
     |
 +---+---+
 |       |
Dog     Cat

Since Dog is subtype of Animal you might ask yourself some questions:

1. Is Function[Dog] subtype of Function[Animal]? Or in other words, can you assign a function that returns a Dog to a function that returns an Animal?
2. Is Function[Dog, Void] subtype of Function[Animal, Void]? Or in other words, can you assign a function that takes a Dog as parameter to a function that takes an Animal as parameter? Or in other words, can you pass a Dog to a function that takes an Animal?
3. Is Array[Dog] subtype of Array[Animal]? Or in other words: Can you assign a list of Dogs to a list of Animals?

The correct kind of variance can prohibit (type-) unsafe assignments and prevent errors. So let's have a look at the four kinds of variance to answer these questions.

The Four Kinds Of Variance

The term variance describes how subtyping between higher kinded types is related to subtyping relations of their type arguments.

Overview

1. covariance: C[S] is a subtype of C[T] if S is a subtype of T (subtyping relation is preserved)
2. contravariance: C[S] is a subtype of C[T] if T is a subtype of S (subtyping relation is reversed)
3. invariance: C[S] is a subtype of C[T] only if types S and T are “equivalent” or subtypes of each other (subtyping relation is ignored)
4. bivariance: C[S] is always a subtype of C[T]

covariance

C[S] is a subtype of C[T] if S is a subtype of T (subtyping relation is preserved)

Question

Is Function[Dog] subtype of Function[Animal]? Or in other words, can you assign a function that returns a Dog to a function that returns an Animal?

Yes, you can. Function return types are covariant. Anything that can retrieve an Animal can retrieve a Dog, since Dog is also an Animal. The opposite is not valid.

contravariance

C[S] is a subtype of C[T] if T is a subtype of S (subtyping relation is reversed)

Question

Is Function[Dog, Void] subtype of Function[Animal, Void]? Or in other words, can you assign a function that takes a Dog as parameter to a function that takes an Animal as parameter? Or in other words, can you pass a Dog to a function that takes an Animal?

No, you could pass a Cat (which is an Animal) to a function that takes an Animal, but you can not pass a Cat to a function that takes a Dog.

However, the opposite applies: Function[Animal, Void] is subtype of Function[Dog, Void]. In other words, you can assign a function that takes an Animal as parameter to a function that takes a Dog as parameter. That's because a function that takes an Animal can take a Dog (which is an Animal).

Hence, function parameters are contravariant.

invariance

C[S] is a subtype of C[T] only if types S and T are “equivalent” or subtypes of each other (subtyping relation is ignored)

Question

Is Array[Dog] subtype of Array[Animal]? Or in other words: Can you assign a list of Dogs to a list of Animals?

No, it is not. Since Array[T] has a method get(index: Number) => T that returns T it is covariant. Since Array[T] has a method add(element: T) => void that takes T it has to be contravariant. Is Array[S] subtype of Array[T]? Due to covariance, S has to be subtype of T. Due to contravariance, T has to be subtype of S. Thus, S and T have to be subtypes of each other. Thereby, arrays are invariant.

bivariance

C[S] is always a subtype of C[T]

For a type parameter to be bivariant, it must only appear bivariantly in a generic. This means either it does not appear at all

interface Pair[A, B] {
    first: A
    second: B
}

// generic function type:
getFirst[A](Pair[A,*]) => A // * represents a bivariant type argument (type is of no concern)

or it appears only as the type argument to instantiate other bivariant generics.

interface I[X] {
    doSomething(I[X]) => I[X]
}

Side note: Bivariance is required in order to be able to infer the unique best solutions of a type argument's variance.