Difference between Covariance & Contra-variance

Question

The question is "what is the difference between covariance and contravariance?"

Covariance and contravariance are properties of a mapping function that associates one member of a set with another. More specifically, a mapping can be covariant or contravariant with respect to a relation on that set.

Consider the following two subsets of the set of all C# types. First:

{ Animal, 
  Tiger, 
  Fruit, 
  Banana }.

And second, this clearly related set:

{ IEnumerable<Animal>, 
  IEnumerable<Tiger>, 
  IEnumerable<Fruit>, 
  IEnumerable<Banana> }

There is a mapping operation from the first set to the second set. That is, for each T in the first set, the corresponding type in the second set is IEnumerable<T>. Or, in short form, the mapping is T → IE<T>. Notice that this is a "thin arrow".

With me so far?

Now let's consider a relation. There is an assignment compatibility relationship between pairs of types in the first set. A value of type Tiger can be assigned to a variable of type Animal, so these types are said to be "assignment compatible". Let's write "a value of type X can be assigned to a variable of type Y" in a shorter form: X ⇒ Y. Notice that this is a "fat arrow".

So in our first subset, here are all the assignment compatibility relationships:

Tiger  ⇒ Tiger
Tiger  ⇒ Animal
Animal ⇒ Animal
Banana ⇒ Banana
Banana ⇒ Fruit
Fruit  ⇒ Fruit

In C# 4, which supports covariant assignment compatibility of certain interfaces, there is an assignment compatibility relationship between pairs of types in the second set:

IE<Tiger>  ⇒ IE<Tiger>
IE<Tiger>  ⇒ IE<Animal>
IE<Animal> ⇒ IE<Animal>
IE<Banana> ⇒ IE<Banana>
IE<Banana> ⇒ IE<Fruit>
IE<Fruit>  ⇒ IE<Fruit>

Notice that the mapping T → IE<T> preserves the existence and direction of assignment compatibility. That is, if X ⇒ Y, then it is also true that IE<X> ⇒ IE<Y>.

If we have two things on either side of a fat arrow, then we can replace both sides with something on the right hand side of a corresponding thin arrow.

A mapping which has this property with respect to a particular relation is called a "covariant mapping". This should make sense: a sequence of Tigers can be used where a sequence of Animals is needed, but the opposite is not true. A sequence of animals cannot necessarily be used where a sequence of Tigers is needed.

That's covariance. Now consider this subset of the set of all types:

{ IComparable<Tiger>, 
  IComparable<Animal>, 
  IComparable<Fruit>, 
  IComparable<Banana> }

now we have the mapping from the first set to the third set T → IC<T>.

In C# 4:

IC<Tiger>  ⇒ IC<Tiger>
IC<Animal> ⇒ IC<Tiger>     Backwards!
IC<Animal> ⇒ IC<Animal>
IC<Banana> ⇒ IC<Banana>
IC<Fruit>  ⇒ IC<Banana>     Backwards!
IC<Fruit>  ⇒ IC<Fruit>

That is, the mapping T → IC<T> has preserved the existence but reversed the direction of assignment compatibility. That is, if X ⇒ Y, then IC<X> ⇐ IC<Y>.

A mapping which preserves but reverses a relation is called a contravariant mapping.

Again, this should be clearly correct. A device which can compare two Animals can also compare two Tigers, but a device which can compare two Tigers cannot necessarily compare any two Animals.

So that's the difference between covariance and contravariance in C# 4. Covariance preserves the direction of assignability. Contravariance reverses it.

It's probably easiest to give examples - that's certainly how I remember them.

Covariance

Canonical examples: IEnumerable<out T>, Func<out T>

You can convert from IEnumerable<string> to IEnumerable<object>, or Func<string> to Func<object>. Values only come out from these objects.

It works because if you're only taking values out of the API, and it's going to return something specific (like string), you can treat that returned value as a more general type (like object).

Contravariance

Canonical examples: IComparer<in T>, Action<in T>

You can convert from IComparer<object> to IComparer<string>, or Action<object> to Action<string>; values only go into these objects.

This time it works because if the API is expecting something general (like object) you can give it something more specific (like string).

More generally

If you have an interface IFoo<T> it can be covariant in T (i.e. declare it as IFoo<out T> if T is only used in an output position (e.g. a return type) within the interface. It can be contravariant in T (i.e. IFoo<in T>) if T is only used in an input position (e.g. a parameter type).

It gets potentially confusing because "output position" isn't quite as simple as it sounds - a parameter of type Action<T> is still only using T in an output position - the contravariance of Action<T> turns it round, if you see what I mean. It's an "output" in that the values can pass from the implementation of the method towards the caller's code, just like a return value can. Usually this sort of thing doesn't come up, fortunately :)

I hope my post helps to get a language-agnostic view of the topic.

For our internal trainings I have worked with the wonderful book "Smalltalk, Objects and Design (Chamond Liu)" and I rephrased following examples.

What does “consistency” mean? The idea is to design type-safe type hierarchies with highly substitutable types. The key to get this consistency is sub type based conformance, if you work in a statically typed language. (We'll discuss the Liskov Substitution Principle (LSP) on a high level here.)

Practical examples (pseudo code/invalid in C#):

• Covariance: Let's assume Birds that lay Eggs “consistently” with static typing: If the type Bird lays an Egg, wouldn't Bird's subtype lay a subtype of Egg? E.g. the type Duck lays a DuckEgg, then the consistency is given. Why is this consistent? Because in such an expression:Egg anEgg = aBird.Lay();the reference aBird could be legally substituted by a Bird or by a Duck instance. We say the return type is covariant to the type, in which Lay() is defined. A subtype's override may return a more specialized type. => “They deliver more.”

• Contravariance: Let's assume Pianos that Pianists can play “consistently” with static typing: If a Pianist plays Piano, would she be able to play a GrandPiano? Wouldn't rather a Virtuoso play a GrandPiano? (Be warned; there is a twist!) This is inconsistent! Because in such an expression: aPiano.Play(aPianist); aPiano couldn't be legally substituted by a Piano or by a GrandPiano instance! A GrandPiano can only be played by a Virtuoso, Pianists are too general! GrandPianos must be playable by more general types, then the play is consistent. We say the parameter type is contravariant to the type, in which Play() is defined. A subtype's override may accept a more generalized type. => “They require less.”

Back to C#:
Because C# is basically a statically typed language, the "locations" of a type's interface that should be co- or contravariant (e.g. parameters and return types), must be marked explicitly to guarantee a consistent usage/development of that type, to make the LSP work fine. In dynamically typed languages LSP consistency is typically not a problem, in other words you could completely get rid of co- and contravariant "markup" on .Net interfaces and delegates, if you only used the type dynamic in your types. - But this is not the best solution in C# (you shouldn't use dynamic in public interfaces).

Back to theory:
The described conformance (covariant return types/contravariant parameter types) is the theoretical ideal (supported by the languages Emerald and POOL-1). Some oop languages (e.g. Eiffel) decided to apply another type of consistency, esp. also covariant parameter types, because it better describes the reality than the theoretical ideal. In statically typed languages the desired consistency must often be achieved by application of design patterns like “double dispatching” and “visitor”. Other languages provide so-called “multiple dispatch” or multi methods (this is basically selecting function overloads at run time, e.g. with CLOS) or get the desired effect by using dynamic typing.

The converter delegate helps me to understand the difference.

delegate TOutput Converter<in TInput, out TOutput>(TInput input);

TOutput represents covariance where a method returns a more specific type.

TInput represents contravariance where a method is passed a less specific type.

public class Dog { public string Name { get; set; } }
public class Poodle : Dog { public void DoBackflip(){ System.Console.WriteLine("2nd smartest breed - woof!"); } }

public static Poodle ConvertDogToPoodle(Dog dog)
{
    return new Poodle() { Name = dog.Name };
}

List<Dog> dogs = new List<Dog>() { new Dog { Name = "Truffles" }, new Dog { Name = "Fuzzball" } };
List<Poodle> poodles = dogs.ConvertAll(new Converter<Dog, Poodle>(ConvertDogToPoodle));
poodles[0].DoBackflip();

Co and Contra variance are pretty logical things. Language type system forces us to support real life logic. It's easy to understand by example.

Covariance

For instance you want to buy a flower and you have two flowers shop in your city: rose shop and daisy shop.

If you ask someone "where is the flowers shop?" and someone tells you where is rose shop, would it be okay? Yes, because rose is a flower, if you want to buy a flower you can buy a rose. The same applies if someone replied you with the address of the daisy shop.

This is example of covariance: you are allowed to cast A<C> to A<B>, where C is a subclass of B, if A produces generic values (returns as a result from the function). Covariance is about producers, that's why C# use keyword out for covariance.

Types:

class Flower {  }
class Rose: Flower { }
class Daisy: Flower { }

interface FlowerShop<out T> where T: Flower {
    T getFlower();
}

class RoseShop: FlowerShop<Rose> {
    public Rose getFlower() {
        return new Rose();
    }
}

class DaisyShop: FlowerShop<Daisy> {
    public Daisy getFlower() {
        return new Daisy();
    }
}

Question is "where is the flower shop?", answer is "rose shop there":

static FlowerShop<Flower> tellMeShopAddress() {
    return new RoseShop();
}

Contravariance

For instance you want to gift a flower to your girlfriend and your girlfrend likes any flowers. Can you consider her as a person who loves roses, or as a person who loves daisies? Yes, because if she loves any flower she would love both rose and daisy.

This is an example of the contravariance: you’re allowed to cast A<B> to A<C>, where C is subclass of B, if A consumes generic value. Contravariance is about consumers, that's why C# use keyword in for contravariance.

Types:

interface PrettyGirl<in TFavoriteFlower> where TFavoriteFlower: Flower {
    void takeGift(TFavoriteFlower flower);
}

class AnyFlowerLover: PrettyGirl<Flower> {
    public void takeGift(Flower flower) {
        Console.WriteLine("I like all flowers!");
    }
}

You're considering your girlfriend who loves any flower as someone who loves roses, and giving her a rose:

PrettyGirl<Rose> girlfriend = new AnyFlowerLover();
girlfriend.takeGift(new Rose());

Links

• Post about generic programming in general
• The same answer for Java programming language