Covariant and Contravariant

Covariant and Contravariant were always one of those complicated concepts that I was running away from! But one day I decided to learn it, and finally, free my soul! Here I describe it in an easy way and hope to help other people to free their soul too!

From wikipedia, the complicated definition (the reason for my fear to learn!) is this:

Within the type system of a programming language, a typing rule or a type constructor is:

covariant if it preserves the ordering of types (≤), which orders types from more specific to more generic;

contravariant if it reverses this ordering;

bivariant if both of these apply (i.e., both I<A> ≤ I<B> and I<B> ≤ I<A> at the same time);

invariant or nonvariant if neither of these applies.

But don't worry, that was the complicated one, this blog is going to make it easy.

The Easy Story

Consider these classes and their inheritance:

class Animal
{
}

class Cat : Animal
{
}

class Lion : Animal
{
}

This is good, as we explicitly said, Cat is subtype of Animal. Now consider some generic classes.

// Represents a PetStore that sell animals of type T, so we
// could call Buy() to get an animal from the store.
class PetStore<T>
{
    T Buy();
}

// Represents trainers capable of training T, so we can call
// Train(animal) method to make the trainer to train the animal.
class Trainer<T>
{
    void Train(T animal)
    {
    }
}

Once you declare a generic class, you are announcing lots of types, so you have these types available:

Trainer<Animal> , Trainer<Cat> , Trainer<Lion> .
PetStore<Animal> , PetStore<Cat> , PetStore<Lion> .

In this case, we have one class, and plenty of types. As these types are not explicitly declared, so their inheritance relationship is not declared explicitly and it should be inferred by the compiler. So the question is this:

Is PetStore<Cat> a subtype of PetStore<Animal> ?

Or a simpler question: Is this type casting valid?

PetStore<Cat> catStore = new PetStore<Cat>();
// Is a cat store a valid animal store?
PetStore<Animal> animalStore = (PetStore<Animal>) catStore;
Animal myAnimal = animalStore.Buy();

This means that we are sure that animalStore.Buy() returns an Animal. Are we!? We know animalStore internally stores an object of type PetStore<Cat> with a Buy method like: Cat Buy() . As Buy returns Cat and Cat is a valid Animal, the whole story makes sense.

Although it seems valid, but most of languages like Java and C# can not infer this fact. Why!? Is the compiler that stupid!? Isn't it obvious that PetStore<Cat> should be a subtype of PetStore<Animal> ? No it's not obvious! The following sample shows that this rule is not valid always.

Let's check the other class: Trainer. Again the same question:

Is Trainer<Cat> a subtype of Trainer<Animal> ?

Or a simpler question: Is this type casting valid?

Trainer<Cat> catTrainer = new Trainer<Cat>();
// Is a cat store a valid animal store?
Trainer<Animal> animalTrainer = (Trainer<Animal>) catTrainer;

Animal animal = new Lion();

animalTrainer.Train(animal);

What's really in animalTrainer variable is a Trainer<Cat> . And what's really behind animal is a Lion . So basically, we are giving a lion to a cat trainer!!! Does is seem valid!? Of course not.

But what happened? Why Trainer<Cat> is not a subtype of Trainer<Animal> although Cat is still a subtype of Animal.

This basic difference is the reason that compilers can not infer the sub typing of generic classes by default.

In fact, in this case the sub typing is inverse:

Trainer<Animal> animalTrainer = new Trainer<Animal>();
// Is a cat store a valid animal store?
Trainer<Lion> lionTrainer = (Trainer<Lion>) animalTrainer;

Loin animal = new Loin();

lionTrainer.Train(animal);

What's really in lionTrainer variable is a Trainer<Animal> , and what's really behind animal is a Lion. So basically, we are giving a lion to a animal trainer. It seems valid. Having someone expert in training animals, and a lion which is an animal too, everything works fine.

A good summary of this concept is this diagram which is available here in Wikipedia:

Implementation in Languages

So as you see, the Trainer characteristic and behavior is different than PetStore. In computer science, they call PetStore a Covariant generic type and Trainer a Contravariant generic type. As this is a characteristics of the type, this is our responsibility to tell about it to the compiler. There are 2 common approaches to handle this situation in different languages:

Declaration-site variance annotations: like C#, Scala and OCaml
Use-site variance annotations (wildcards): like Java

Declaration-site variance annotations

As the Covariant/Contravariant is a characteristic of the Type, we could specify it when declaring the type. This is happening by in/out keywords in C# and +/- keywords in Scala and OCaml like:

// Sample in C#

interface PetStore<out T>
{
    T Buy();
}

interface Trainer<in T>
{
    void Train(in T animal)
    {
    }
}

Use-site variance annotations (wildcards)

In this approach, the situation is handled when the casting is happening, like wildcards in Java:

// Contravariant
Trainer<? super Cat> catTrainer = animalTrainer;

// Covariant
PetStore<? extends Animal> animalTrainer = catTrainer;

Comparing declaration-site and use-site annotations

There is a good comparison available here. But briefly it can be summarized as this:

As Covariant/Contravariant is one of the type characteristics, the declaration-site is a better approach.
The decision about use-site approach in Java is taken because of some backward compatibility reasons.

Also from the reference:

In a conference presentation Joshua Bloch criticized them as being too hard to understand and use, stating that when adding support for closures "we simply cannot afford another wildcards". Early versions of Scala used use-site variance annotations but programmers found them difficult to use in practice, while declaration-site annotations were found to be very helpful when designing classes. Later versions of Scala added Java-style existential types and wildcards; however, according to Martin Odersky, if there were no need for interoperability with Java then these would probably not have been included.

Wasn't that easy!? I don't know why I was so scared to learn such a simple concept in these years!