Variance

Last modified on February 3, 2020 by Alex


Why the status quo sucks

For proper variance polymorphism with higher-kinded types you need some way to compose variances. For example, consider the following type alias:

Depending on whether F is covariant or contravariant, Foo[F, A] will be either covariant or contravariant in A:

We can, of course, force a particular kind of variance using @uncheckedVariance annotation:

But that is highly undesirable, since we can accidentally set incorrect variance.

A solution: variance variables

Instead, it would be nice to have variance annotations with variables:

Here, variance of A is the same as the variance of F’s parameter. If F is covariant, Foo is covariant in A, and vice-versa.

Now consider a more complex case:

Because F[A] is in a negative position, A’s variance is the opposite of F’s variance.

An even more complex case:

Since A is inside both F and G, it’s variance is the product of the variances of F and G.

Variance composition

Now remember that Scala has covariant (cv), contravariant (ct), and invariant (inv) type constructors. Here is how they compose:

Weakening

Consider Foo once again:

Notice that even though A has the same variance as F’s parameter, we are always free to weaken the variance annotation and make A invariant like so:

In a slightly different scenario,

A does not appear in the RHS of the type declaration, so we are free to assign any variance to it (there are no constraints on its variance).

In general, variances form a partial order:

Such that a weaker variance can always be replaced with a weaker variance in any type declaration.

We can see that our partial order is bounded from below, but it is not bounded from above, which is unsatisfying.

We can bound it from above by introducing

Phantom variance

F[_] is covariant if for any A <: B, the compiler is free to assume F[A] <: F[B]. It is contravariant if for any A <: B, the compiler is free to assume F[B] <: F[A]. It is invariant if no matter the relationship between A and B, the compiler is not free to assume a subtyping relation between F[A] and F[B].

Phantom variance on the other hand means that for any A and B, F[A] <: F[B] and F[B] <: F[A]. In fact, F[A] = F[B].

You have phantom variance whenever a type variable does not occur anywhere in the type declaration’s RHS, so it can be replaced with any other type:

Phantom variance completes our partial order of variances acting as the top element:

And it composes as if it is an annihilator:

Parallel composition

It turns out that in order to complete the picture, we need one more composition operator. Consider the following example:

What is w here? We can see that w <= u and w <= v. If v = ct and v = cv, there is only one solution to these inequalities, w = inv. If v = ph and v = cv, there are two solutions, w = cv and w = inv. In general, we can say that w <= v min u, where we are using our partial order (and in fact, a lattice) of variances.

Instead of writing u min v, we will write it as u \/ v:

Automatic variance annotation inference

It is straightforward to infer the weakest possible variance annotations in all cases completely automatically. E.g. consider:

All annotations can be inferred automatically:

A developer might decide to weaken them or perhaps even strengthen them with @uncheckedVariance:

Such weakening of type declarations can be done in an automated fashion as well, because the algebra of variances is rather simple.