Covariant and Contravariant Types made simple

The 101 of inheritance tells us that a Cat is an Animal and Animal is an Organism. Thanks, we already know.

But how about a Parametrized Type (Generic) TakeCare<Animal>? Can we pass a TakeCare<Cat> when a TakeCare<Animal> is expected? How about TakeCare<Organism>?

Type Variance allows us to answer the question.

What’s Type Variance?

I’m considering Parametrized Types here (or Generics), which is the most common case where variance matters. In this case, Variance is a property of a Type that describes how it relates to its Parametrized Types in terms of subtyping.

I will use the notation T <: U to describe that T is a subtype of U (or U is a supertype of T).

The question that variance answers is: Given a Type A and its supertype B, how does the Parametrized Types P[A] and P[B] relates in terms of subtyping? Or, given A <: B what can we say about subtyping of P[A] and P[B]? Simple:

• Covariant: P[A] <: P[B]
  The Parametrized Types have the same subtyping relationship of the Type parameters. Hence the co- latin prefix, and the P[+A] scala syntax (later on the P<out A> C# syntax).
• Contravariant: P[A] :> P[B]
  The Parametrized Types have the opposite subtyping relationship of the Type parameters. Hence the contra- latin prefix, and the P[-A] scala syntax (later on the P<in A> C# syntax).
• Invariant: P[A] /noway/ P[B]
  There’s no subtyping relationship. Hence the in- latin prefix, the P[A] scala syntax, and the P<A> C# syntax.

One step further, Function Types Subtyping

Next question to answer: given two function types that have a subtyping relationship, what can we say about input and output types variance? Remember the in/out C# prefix? There’s a hint there. Let’s go.

Let’s assume we have two functions that are in a subtyping relationship like this:

(B => U) <: (A => T)

The function type B=>U is a subtype of the function type A=>T, with B and A being the input types and U and T the output types.

So, what kind of subtyping relationship should respectively A, B and U, T be in? Paraphrasing Liskov, two types are in a subtyping relationship if everything one can do with the supertype (the function A => T), one should be able to do it with the subtype (B => U) without changing the behavior.

Now take a breath and read.

If we can use A as the input of the supertype A => T, can we pass A to the subtype B = > U without changing the behavior? Yes, if A is a subtype of B. Great, we found the first condition: A <: B.

How about the output types? If we provide A to the subtype B => U — which is OK for the A <: B relationship — we get the a type U. Have we changed the behavior? No, if U can be qualified as T. And when is it the case?
When U <: T.
Bingo, we have the input and type conditions to be met!

To summarise:

Given the subtyping relationship
A <: B and U <: T
Then exists the function subtyping relationship
(B => U) <: (A => T)

How can we describe in terms of variance the input and output type relationship?

Input is contravariant, because of the inverted subtyping relationship:

• B is in the subtype function B => U
• A is in the supertype function A =>T

Output is covariant, because of the same subtyping relationship:

• U is in the subtype function B => U
• T is in the supertype function A => T

Functions are very open minded with the input. But very picky when comes to the output.

Why should I care?

Because compilers will do some useful magic to protect you from less elegant implementations (you don’t want another Java ArrayStoreException).

Oh, and because now you can get why the C# syntax has in and out types prefixes to describe contra- and co- variant types.