# Variance

## 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`

:

```
// Actually covariant.
type Foo1[A] = Foo[Option, A]
// Actually contravariant.
type Foo2[A] = Foo[Function1[?, Boolean], A]
```

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

annotation:

```
import scala.annotation.unchecked.{ uncheckedVariance => uV }
type Foo1[+A] = Foo[Option, A @uV]
type Foo2[-A] = Foo[Function1[?, Boolean], A @uV]
```

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:

```
// These are like 1 and -1 w.r.t. multiplication.
ct * ct = cv
cv * cv = cv
cv * ct = ct
// Invariance acts like a zero (an annihilator)
cv * inv = inv
ct * inv = inv
inv * inv = inv
// Variance composition is commutative.
X * Y = Y * X
```

## 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:

```
type Foo[a G[b _], c F[d _], e L, f A] = (G[(L, F[A]) => Bool], F[L])
// a <= cv
// e <= ct * b * cv
// c <= ct * b * cv
// f <= d * ct * b * cv
// c <= cv
// e <= d * cv
// a = cv
// e = min(ct * b * cv, d * cv) = min(-b, d) = (-b) \/ d
// c = min(ct * b * cv, cv) = min(-b, cv)
// f = - b * d
type Foo[+ G[b _], (-b \/ +) F[d _], (-b \/ d) L, - b d A] =
(G[(L, F[A]) => Bool], F[L])
```

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.