Introduction
Many langauges support subtyping - this allows us to express that a type Apple is a subtype of Fruit. Notationally, we say T < S. Subtyping manifest itself as subclass in most programming language concepts.
Suppose we have the following:
class Fruit {}
class Apple extends Fruit {}
class Orange extends Fruit {}
class GreenApple extends Apple {}
Then we have Apple < Fruit. In simple English, we can think of this as whenever we expect a type Fruit, we can use the type Apple. Or think of it as an Apple is a Fruit.
The term variance refers to how subtyping between complex types (e.g. types that takes types as parameters) relate to subtyping between their components.
The topic of covariance comes into play when we ask question such as is []T < []S, more concretely []Apple < []Fruit. If that is true, then we we say that List constructor is covariant.
The conflict
Take the example of list constructor and we shall see why both covariant and contravariant can give us unsafe programs.
Covariant list (Problem when writing)
If Apple < Fruit, then []Apple < []Fruit. That is we treat []Apple as a []Fruit. But we clearly cannot insert an Orange into []Apple.
Contravariant list (Problem when reading)
Similarly, if we treat []Fruit as []Apple, then we cannot guarantee that elements from the former contains just Apples.
Java list
In Java, list is covariant but generics is invariant.
// List is covariant so this will compile.
// But writing to the list can cause runtime exceptions.
Fruit[] f1 = new Apple[2];
f2[0] = new GreenApple(); // OK
f2[1] = new Apple(); // OK
// Generics is invariant so this won't compile.
// The way to reason about the following is that the type (List of Fruit)
// is not the same as the type (List of Apple) so they cannot be assigned.
List<Fruit> f2 = new ArrayList<Apple>();
The invarance of it provides safety at compile time (instead of runtime).
Using covariance
Sometimes it can be useful to treat []Apple as a []Fruit. We can do that with the help of the ? syntax, as long as we don’t mutate the list. Recall that covariance has problems when writing to it.
// However, one can use the wildcare to give some flexibility.
// Now we can say that the list of Apple is a list of a specific kind of fruit.
// This gives us the safety that what we get from f3 is a fruit.
List<? extends Fruit> f3 = new ArrayList<Apple>();
Using contravariance
Similarly, when we want to write to the new type, we can use contravariance.
// Here we can
void writeTo(List<? super Apple> apples) {
apples.add(new Apple());
apples.add(new GreenApple());
}
Conclusion
We can use the concepts of variance to help us determine new types that are type safe.
Additional reading
Aside
If we were to think of classes as a collection of fields, then we can think of the left side as being more specific than the right.
{p:int, q:int} <: {p:int} <: {}
Interestingly, we can get safety if we allow covariance immutable list since the danger only happens when we’re trying to write to the list.
Let’s think about the semantics of subtyping on functions:
$$\text{subtyping-function} \hspace{2em} \frac{T_1’ <: T_1 \hspace{5em} T_2 <: T_2’}{T_1 \rightarrow T_2 <: T_1’ \rightarrow T_2’}$$
The function type constructor is both covariant and contravariant.