Posted on January 11, 2019
Given a polymorphic type, like
List, what can we say about the relationship between different usages of that type? If
B are related, is
List[A] related to
List[B]? Variance is the word for this type of relationship, and it turns out there are a few different answers to that question, depending on the type you’re asking about.
Probably the most familiar situation is when the parameterised types are related in the same way as the parameter. This is the type of variance exhibited by most “container” types, like
A is annotated with
+, so it’ll be treated as covariant. This allows you to use a
List[Cat] any time you need a
List[Animal]. A list of
Cats is a list of
Animals, because every
Cat is an
Animal. The subtype relationship of the container goes in the same direction as the subtype relationship of the elements. (In C#
+ is pronounced
out, as in
Variance is visible even in non-subtyping-based languages. Haskellers’ll be familiar with covariant functors. It’s the type of functor exhibited the the standard
This chimes with the intuition that a functor
f is a container of sorts. If you can write a function to convert each
a in the container into a
fmap can convert a container of
as into a container of
bs by converting each item in the container.
In general, a type is covariant if its parameter is used as an output. An object which produces
Cats can be used to produce
Animals. All you have to do is ignore the cattiness of the animals you get out of the producer.
Contravariance, covariance’s evil twin, is the word for when the parameterised types are related in the opposite way as the parameters. Scala’s
Ordering, which determines which way round to put two objects (like C#’s
IComparer), is an example of a contravariant type.
- symbol denotes a contravariant parameter, allowing us to use an
Ordering[Animal] as an
Ordering[Cat]. (C#ers say
in, as in
IComparer<in T>.) If you know how to compare two
Animals (perhaps by comparing their cuteness), you can certainly compare two
Cats. The subtype relationship of the comparers goes in the opposite direction to that of the parameters.
The class of contravariant functors in Haskell is just like
Functor but with the direction of one of the arrows flipped.
If you can turn
as, then you can turn a comparer of
as into a comparer of
bs by converting the
as before they go into the comparer. Note how
f is applied to
p’s inputs in the implementation of
In general, a type is contravariant if its parameter appears as an input. An object which consumes
Animals can be used to consume
Cats. All you have to do is forget about the cattiness of the animals before you put them into the consumer.
Julie Moronuki has the best explanation of contravariance that I know of.
Invariance is the word for when there’s no relationship at all between different usages of a parameterised type.
In Scala a type parameter unadorned with a sign is invariant. The following mutable set type is invariant:
In general, a type is invariant if its parameter appears as both an input and an output. You can’t use
Set covariantly, because
A appears as an input to
contains, and you can’t use it contravariantly because
A appears in
items’s output. There’s no subtyping relationship between the parameter and the type. A
Set[Cat] is not a
Set[Animal]. If it was, you’d be allowed to upcast it and then call
add with a
The same logic applies to the opposite situation. A
Set[Animal] is not a
Here’s a Haskell class defining
You have to be able to map
bs in both directions to convert an invariant functor. This implies that the functor both consumes and produces
as: you map items on the way out and on the way in.
Note how we use
f on the output of
g on the inputs.
The only time I’ve actually seen this class used is in Ed Kmett’s old article about attempting to represent higher-order abstract syntax generically.
Let me spell out the similarity between
Invariant functors and Scala’s subtype invariance. For
Operation a to be convertible to
a must be convertible to
b must be convertible to
Set[A] to be a subtype of
A must be a subtype of
B must be a subtype of
A (that is, they must be the same type).
Note that variance is a property of the type parameter (
A), not the type constructor (
Ordering). A given type constructor may have multiple parameters with different variances.
Function1[-A, +B], for example.
An object which produces a producer of
As effectively produces
As. A type with a covariant type as an output is itself covariant.
Consuming a producer of
As is basically the same as consuming
As. A type which has a covariant type as an input is contravariant.
Producing a consumer of
As is like consuming
As. A type with a contravariant type as an output is contravariant.
A consumer of consumers is itself a producer. (You have to be able to produce
As in order to feed them to the consumer.) A type with a contravariant type as an input is covariant.
Mnemonically, you can think of input parameters as meaning “times -1”.
As as its inputs, so
Ordering is negative.
Sortable takes a (negative)
Ordering as an input, so it’s positive (-1 * -1 = 1). Printer takes a (positive)
List as input, so it’s negative. This explains Scala’s choice of
- as the syntax for its variance annotations.
The Semilattice of Variances
Now, it turns out that these three types of variance have a relationship to each other. Invariance generalises both covariance and contravariance. Covariant things are also invariant, and contravariant things are also also invariant.
If I was in the business of redesigning Haskell’s libraries, I’d even consider making
Invariant a superclass of
So there’s this interesting relationship between the three types of variance. They form a little semilattice, of which
Invariant is the supremum.
But, hmm, the picture seems asymmetric. Is variance really only a semilattice? Or is there something lurking at the bottom of that picture?
Looking at the code above, it appears that
Contravariant both specialise
Invariant by ignoring one of
Invariant’s function parameters. What if we ignored both of them?
This strange class says that you can map an
f a to an
f b without needing to map
bs at all! Intuitively, you can only convert
f a to
f b for free when
f doesn’t mention
a anywhere in its body.
A functor is
Invariant when it has
as both as inputs and outputs.
Invariant by promising that
f doesn’t have any input
as, so all you need to do is map the outputs.
Invariant by promising that there are no output
as and all you need to do is map the inputs.
Phantom, being a special case of both covariance and contravariance, guarantees that there are no
as at all in the
So the four types of variance form a nice lattice.
For completeness, here’s the proof that the superclass constraints make sense:
Phantom types show up every now and then in Haskell. They’re used to decorate ordinary values with additional type-level information, either to layer on additional type safety or to give GHC a hint for type inference.
Haskell is the only language I know of with proper support for phantom types, in its role system. (
Phantom roughly means
forall a b. Coercible (f a) (f b).) Scala doesn’t support it, but it’d mean that a type is always a subtype of any other instantiation of that type, even if the type arguments have no relationship.
Proxy[A] is always a subtype of
Proxy[B] (and vice versa!), even when
B are nothing to do with each other. To a certain extent this defeats the purpose of phantom types. It also breaks antisymmetry — two different types can both be a subtype of each other — so subtyping is no longer a partial order. As a language feature, phantom variance probably isn’t actually all that desirable.