Covariance and Contra­variance

· 7 min

A dog is an animal. Is a list of Dogs a list of Animals?

It depends on how you use it, and what need from it.

Generic Types

Generics are a type system feature which allows instantiating a generic type with type arguments. A common example is List<T>, which stores instances of its type argument T as a sequential collection.

List<int> numbers = new() {1, 2, 3};
int number = numbers[0];  // 1

List<T> is mutable. We can add items using its Add method.

numbers.Add(4);
number = numbers[3];  // 4

Some generic classes are immutable. IEnumerable<T> is a generic sequence of T, which provides a read-only view of a List<T> whose entries come one at a time.

IEnumerable<T> sequence = numbers;

Assignment Compatibility

In an inheritance relationship there are (at least) two classes involved: the base class and the derived class. A derived class instance is always substitutable for a base class instance, so the derived class is said to be a subtype of the base class supertype.

class Animal
{
    public virtual string GetNoise() => "???";
}

class Dog
{
    public override string GetNoise() => "Woof!";
}

void SayNoise(Animal animal) {
    Console.WriteLine(animal.GetNoise());
}

Animal animal = Dog();
SayNoise(animal);  // "Woof!"

In this example Dog is a subtype of Animal. Any time an Animal is needed, a Dog may be used instead. That is to say, a Dog is substitutable for an Animal.

What about a collection of animals? Is a list of Dogs substitutable for a list of Animals?

Covariance

A generic type S is said to be covariant if, given type arguments T and U where T is a subtype of U, S<T> is a subtype of S<U>. For example, IEnumerable<Dog> is a subtype of IEnumerable<Animal> because Dog is a subtype of Animal and IEnumerable<T> is covariant.

This makes sense. Since Dog is always substitutable for Animal, a function observing a sequence of animals won’t mind if some or all of them are dogs.

void SayNoises(IEnumerable<Animal> animals) {
    foreach (Animal animal in animals) {
        SayNoise(animal);
    }
}

List<Dog> dogList = new() {Dog(), Dog(), Dog()};
IEnumerable<Dog> dogs = dogList;
IEnumerable<Animal> animals = dogs;
SayNoises(animals);

Invariance

Now let’s imagine that I want to create a list containing other kinds of household pets. To accommodate cats, we’ll create a Cat class.

class Cat : Animal
{
    public override string GetNoise() => "Meow!";
}

Let’s add them all to a list of pets.

void AddDogs(List<Animal> pets) {
    pets.Add(Dog());
    pets.Add(Dog());
    pets.Add(Dog());
}

void AddCats(List<Animal> pets) {
    pets.Add(Cat());
    pets.Add(Cat());
}

List<Animal> pets = new();
AddDogs(pets);
AddCats(pets);

So far so good. Let’s take our dogList from earlier and add more dogs to it.

AddDogs(dogList)  // Error!

Wait, what? Why can’t I add dogs to a list of dogs? The problem is that AddDogs doesn’t work with List<Dog>– it works with List<Animal>. List<T> is not covariant, it is invariant. List<Dog> is not a subtype of List<Animal> in the way that IEnumerable<Dog> is a subtype of IEnumerable<Animal>. AddDogs expects a List<Animal>, for which List<Dog> is not substitutable.

List<Animal>Animal[] entriesAnimal this[int index]void Add(Animal)void RemoveAt(int index)List<Dog>Dog[] entriesDog this[int index]void Add(Dog)void RemoveAt(int index)List<Cat>Cat[] entriesCat this[int index]void Add(Cat)void RemoveAt(int index)IReadOnlyList<Dog>Dog this[int index]IReadOnlyList<Animal>Animal this[int index]IReadOnlyList<Cat>Cat this[int index]
IReadOnlyList<Animal> Subtype Hierarchy
(Source) (Download)

List<Dog> and List<Animal> are both subtypes of IEnumerable<Animal>, so either can be used wherever an IEnumerable<Animal> is required. However List<Dog> cannot be used wherever a List<Animal> is required.

But why does the subtype hierarchy look this way? Why can’t List<Dog> be a subtype of List<Animal> directly, instead of going through this IEnumerable path? Why isn’t List<T> covariant?

It comes down to mutability. Since List<T> is mutable, we can add instances of T to it. Remember the rule about assignment compatibility: we can substitute any instance of a subtype for an instance of the supertype. Since Dog and Cat are both subtypes of Animal, we can add either to a List<Animal>.

List<Animal> animals = new();
animals.Add(Dog());
animals.Add(Cat());

If List<T> were covariant, List<Dog> would be a subtype of List<Animal> and the following would be possible:

List<Dog> dogs = new();
dogs.Add(Dog());
List<Animals> animals = dogs;
animals.Add(Cat());  // !!!

See the problem? animals is just a reference to dogs, and we tried to add a Cat to it. List<Dog> can’t store cats, it can only store dogs. Therefore a mutable collection can never be covariant 1. The C# compiler will not allow dogs to be assigned as a value to a variable of type List<Animal>.

This problem goes away if the collection is immutable because it is now impossible to add a cat to a list of dogs— there is no Add method on IEnumerable<T>.

Contravariance

This idea of covariance doesn’t just apply to container types; it is relevant to any generic type with type parameters which have a subtype/supertype relationship. Consider Action<T>, which represents a callable function with a single argument of type T and no return value.

Action<Animal> speak = SayNoise;

Is Action<T> covariant? Can we substitute Action<Dog> for Action<Animal>?

void DogSpeak(Dog dog)
{
    Console.WriteLine($"The dog says {dog.SayNoise()}");
}

Action<Dog> speakDog = DogSpeak;
Action<Animal> speakAnimal = speakDog;

Animal cat = Cat();
speakAnimal(cat);  // !!!

This won’t work. DogSpeak requires a Dog, and by substituting Action<Dog> for Action<Animal> we can now provide a Cat instead.

The opposite could work though: a function expecting Animal would be happy to receive a Dog. The Action<Dog> interface forces callers to provide a subset of possible Animals (i.e., Dogs), but can’t add anything that a function expecting an Animal would be unprepared to handle.

Action<Animal> speakAnimal = SayNoise;
Action<Dog> speakDog = speakAnimal;

Animal dog = Dog();
speakDog(dog);

Action<Animal> is substitutable for Action<Dog>! They have an assignment compatibility relationship opposite that Animal and Dog do. This reversal of subtype/supertype relationship in the generic type means that Action<T> is contravariant.

Action<Animal>Action(Animal)Action<Dog>Action(Dog)Action<Cat>Action(Cat)
Action<Animal> Subtype Hierarchy
(Source) (Download)

Defining Covariance and Contravariance

This property of co- and contravariance isn’t something the compiler can determine automatically. It is opt-in, by declaring the type arguments as out (covariant) or in (contravariant). The keywords provide a hint as to how the type argument may be used. Covariant type arguments can only be outputs (i.e., method return types), and contravariant type arguments can only be inputs (i.e., method parameter types).

interface ICovariant<out T>
{
    T GetSomething();
}

interface IContravariant<in T>
{
    void DoSomething(T arg);
}

Consider the following example

List<Dog> dogList = new() { Dog(), Dog() };
IEnumerable<Dog> dogSequence = dogList;
IEnumerable<Animal> animalSequence = dogSequence;

Action<Animal> animalAction = animal => Console.WriteLine(animal.SayNoise());
Action<Dog> dogAction = animalAction;

We can conceptualize the subtype relationships by imagining that the supertype “contains” the subtype. It doesn’t really, but we can think of the covariance and contravariance relationships as “wrapping” the inner type.

IEnumerable<Dog>IEnumerable<Animal>IEnumerable<Dog>Action<Dog>List<Dog>List<Dog>Action<Animal>Action<Dog>Action<Animal>List<Dog>iterate Dogsiterate Dogsiterate Dogsaccept Dogaccept Dog accept Dogiterate Dogsiterate Dogsiterate Animalsaccept Animal
Possible Datapaths
(Source) (Download)

Here we see that the innermost List<Dog> can “forward” its contents to the enclosing IEnumerable<Dog>, which can then forward them to the enclosing IEnumerable<Animal>, because IEnumerable is covariant. The output of IEnumerable<Dog> is a Dog, which we can use in an Action<Dog> directly. The output of IEnumerable<Animal> is, in this case, a Dog under the hood, but the IEnumerable<Animal> interface hides this and presents the Animal supertype instead. This cannot be used in an Action<Dog>, but can be used in Action<Animal>. However because in this case our Action<Dog> is itself a “wrapper” around an Action<Animal>, Dogs passed to it are substituted for Animals in the enclosed Action<Animal>.

Notice that arrows only ever leave IEnumerable blocks and only ever enter Action blocks. If it were possible to pass an Animal into an IEnumerable<Animal>, then it couldn’t be covariant because an underlying object expecting Dogs could receive arbitrary Animals— (just like a List<Dog> could if used as a List<Animal>). Similarly, if it were possible to return an Animal from an Action<Animal>, then it couldn’t be contravariant because it could return arbitrary Animals to callers expecting Dogs.

Summary


  1. The problem is actually due to “input” mutability. A remove-only list is mutable, but can still be covariant because there is never an opportunity to insert an invalid item type to the collection. I address this in more detail later.

    RemoveList<Animal>void RemoveAt(int index)Animal this[int index]RemoveList<Dog>void RemoveAt(int index)Dog this[int index]RemoveList<Cat>void RemoveAt(int index)Cat this[int index]
    RemoveList<Animal> Subtype Hierarchy
    (Source) (Download)
     ↩︎