Extra attributes on post: XmlAttr(name=original_url, value=String(value=https://gitter.im/typelevel/general?at=5bcb6bfa6e5a401c2da237e9))
The status quo situation with variances in Scala sucks. Why?
For proper variance polymorphism with higher-kinded types you need some way to compose variances. For example, consider the following type alias:
type Foo[F[_], A] = F[A]
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.
1. A solution: variance variables
Section missing id
Instead, it would be nice to have variance annotations with variables:
type Foo[+F[v _], v A] = F[A]
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:
type Funky[-F[v A], -v A] = F[A] => Boolean
Because F[A] is in a negative position, A's variance is the opposite of F's variance.
An even more complex case:
type Compose[+F[v A], v G[u A], v u A] = F[G[A]]
Since A is inside both F and G, it's variance is the product of the variances of F and G.
2. Variance composition
Section missing id
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
2.1. Weakening
Section missing id
Consider Foo once again:
type Foo[+F[u _], u A] = F[A]
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:
type Foo[+F[u _], A] = F[A]
In a slightly different scenario,
type Foo[+F[u _], v A] = F[Unit]
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:
ct >= inv
cv >= inv
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.
2.2. Phantom variance
Section missing id
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:
type Foo[+F[u _], v A] = F[Unit]
Phantom variance completes our partial order of variances acting as the top element:
ph >= ct >= inv
ph >= cv >= inv
And it composes as if it is an annihilator:
// Phantom variance is zero
ph * X = ph
2.3. Parallel composition
Section missing id
It turns out that in order to complete the picture, we need one more composition operator. Consider the following example:
type TupleK[+F[v A], +G[u A], w A] = (F[A], G[A])
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:
type TupleK[+F[v A], +G[u A], (u \/ v) A] = (F[A], G[A])
3. Automatic variance annotation inference
Section missing id
It is straightforward to infer the weakest possible variance annotations in all cases completely automatically. E.g. consider:
type Foo[G[_], F[_], L, A] = G[(L, F[A]) => Bool]
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:
type Foo[G[b _], (-b \/ +) F[d _], L, - b d A] =
(G[(L, F[A]) => Bool], F[L])
Such weakening of type declarations can be done in an automated fashion as well, because the algebra of variances is rather simple.