Covariance, Contravariance, and Invariance — The Ultimate Python Guide

[s02e03] CSI: Python Type System

Published in

Daftcode Blog

10 min readNov 28, 2018

This blog post is about covariance, contravariance, and invariance of Python types. I define these concepts and explain them in detail. Every step is accompanied by a fairly straightforward code snippet. I aim to show that the knowledge of these concepts helps to write more reliable code and it is beneficial to all Python programmers.

This is the third part of a blog post series about contravariance and issues related to it. This part is self-contained, though, and can be read separately. The first two parts are devoted to understanding (s02e01) and fixing (s02e02) a specific contravariance-related bug.

If you are new to Python type annotations, I suggest reading my two introductory blog posts first: s01e01 and s01e02.

There are some formalisms in this post, yet they are quite straightforward. I use <: symbol, which reads “is a subtype of” (i.e. subtype is always at the pointy end 🗡 😉). If you are not sure what subtyping is or how it differs from subclassing, just read this and this part of s01e01 blog post.

All code is compatible with Python 3.6+. I use mypy 0.641 type checker.

Covariance

Tuple

Let’s say we have a tuple of Dogs and a tuple of Animals. Their types are Tuple[Dog, ...] and Tuple[Animal, ...], respectively (for a reminder about Tuple type, see here). Every object with the type of Tuple[Dog] can be safely assigned to a variable of the type Tuple[Animal], but not the other way around:

Why the error is reported? It's because animals tuple could contain other animals than dogs. (And in our code in fact it does: an_animal.) Therefore, the type of dogs, which is Tuple[Dog, ...], could be compromised if we assigned an object of Tuple[Animal, ...] type to it. (And in our code in fact it is assigned.)

On the other hand, mypy is happy with animals = dogs assignment. It’s because every element of dogs is a Dog and, due to tuple’s immutability, cannot be anything else. Therefore, it can be used where an object of the type Animal is expected, as Dog is a subtype of Animal. Thus Tuple[Dog, ...] <: Tuple[Animal, ...].

More generally:

Tuple[SubType, ...] <: Tuple[SuperType, ...],
for SubType <: SuperType.

Similarly, in the case of multiple-type tuples:

Tuple[SubType1, SubType2, etc.] <: Tuple[SuperType1, SuperType2, etc.],
for SubType1 <: SuperType1, SubType2 <: SuperType2 (etc.).

Definition of Covariance

The property of Tuple type we have just discovered is called a covariance. Or, more precisely: Tuple is covariant in all its arguments. The formal definition of the covariance is as follows (I slightly modified the definition from mypy docs):

Generic type GenType[T, ...] is covariant in type variable T
if GenType[SubType, ...] <: GenType[SuperType, ...],
for SubType <: SuperType.

A generic type is, basically, a type that takes other types as its parameters, in square brackets, like Tuple, List,Union (see mypy docs). In my first blog post about typing, I called it a “complex type”.

In Python, most immutable containers are covariant. Tuples and frozensets (their type is FrozenSet) are the most significant ones. But there are other covariant types as well.

Union

Union type is covariant in all its arguments:

Union[SubType1, SubType2, etc.] <: Union[SuperType1, SuperType2, etc.],
for SubType1 <: SuperType1, SubType2 <: SuperType2 (etc.).

The covariance of Union basically works the same way as the covariance of Tuple. Let’s say we have two pairs of types: Dog <: Animal and Meat <: Food. It’s safe to use an object of the type Union[Dog, Meat] where an object of the type Union[Animal, Food] is expected, but not the other way around. So, it’s okay to assign an object of the type Union[Dog, Meat] to a variable of the type Union[Animal, Food], but not vice versa.

Return Type of Callable

The case of Callable is a little bit more interesting. We can look at Callable type from two points of view: types of its arguments and the type of its return value.

As for the type of return value, let’s look at the following functions. Both are getting dogs and animals from, say, external services.

Now, it’s safe to use get_dog(returning a Dog) wherever get_animal (returning an Animal) is expected.

some_animal: Animal = get_animal()

Type of some_animal is Animal. get_animal can safely be switched with get_dog, then. It's because it will return a Dog which can be safely used wherever Animal is used because Dog <: Animal. So Callable[[], Dog] <: Callable[[], Animal], or generally:

Callable[[], SubType] <: Callable[[], SuperType],
for SubType <: SuperType.

So Callable is covariant in the return type.

In more general terms, anything that provides something — producer, factory, constructor, writer, etc. — is covariant in the type of the objects it provides. It needs to be read-only with regard to the provided objects, though.

Contravariance

Definition of Contravariance

Contrary term to “covariance” is “contravariance”. It’s defined as follows:

Generic type GenType[T, ...] is contravariant in type variable T
if GenType[SuperType, ...] <: GenType[SubType, ...],
for SubType <: SuperType.

The definition is almost the same as of “covariance”, but with <: relation switched. Let’s get back to Callable.

Arguments of Callable

The other way of looking at Callable is from the types of its arguments point of view. It turns out — and we will see why in a second — that in the case of function’s arguments, subtyping works the other way around compared to plain objects:

Callable[[SuperType], None] <: Callable[[SubType], None],
for SubType <: SuperType.

So, Callable is contravariant in the argument types. Take note that for Callable contravariance works for an arbitrary number of arguments, as long as they are in subtyping relationships in a pairwise fashion:

Callable[[SuperType1, SuperType2, etc.], None] <: Callable[[SubType1, SubType2, etc.], None],
for SubType1 <: SuperType1, SubType2 <: SuperType2 (etc.).

Let’s find out why Callable is not covariant but contravariant in the argument types, then. (The following part is the essence of s02e01 post. Look there for more examples and explanations.)

Take a look at the following code:

Can we assign animal_run = dog_run? That is: can we safely use dog_run wherever animal_run is expected? If we could, it’d mean that Callable[[Dog], None] is a subtype of Callable[[Animal], None]. It turns out we cannot safely make the assignment. If we could, it would be possible to use dog_run on an incompatible object, say, a Kangaroo.

Why mypy reports this error? So, make_animal_run gets two arguments: Bob, a Kangaroo (and it indeed is type-safe to pass him here, since Kangaroo <: Animal) and a dog_run — a Callable[[Animal], None]. Now, inside make_animal_run function dog_run function is to be called on kangaroo Bob. It’s incorrect since dog_run can only be called on a Dog and its subtypes. Therefore, we cannot safely pass dog_run to make_animal_run. For this reason, Callable[[Dog], None] is not a subtype of Callable[[Animal], None]. And this, in turn, leads to the conclusion: Callable is not covariant in the argument types.

What about the contravariance? Can we assign dog_run = animal_run? That is: can we safely use animal_run wherever dog_run is expected?

animal_run accepts an Animal, so it needs to work with a Dog, since Dog <: Animal. Thus, it’s safe to use animal_run when dog_run is expected. Therefore, Callable[[Animal], None] <: Callable[[Dog], None]. As a consequence, Callable is contravariant in the argument types.

So now you understand what “function is covariant in the return type, but contravariant in the argument types” means. You nerd! 🤓

In more general terms, anything that takes something— consumer, sink, reader, listener, etc. — is contravariant in the type of the objects it takes. It needs to be write-only with regard to the taken objects, though.

Invariance

Definition of Invariance

An invariant type is neither covariant nor contravariant. More formally:

Generic type GenType[T, ...] is invariant in type variable T if GenType is neither covariant in type variable T nor contravariant in type variable T.

List

Yes, there’s no mistake, List is not like Tuple, which is covariant. List is neither covariant nor contravariant. I will use this code to show it:

All Animals, including Dogs and Kangaroos, can eat. Only Dogs can bark, and only Kangaroos can leap.

Let’s get the obvious out of the way — List type is not contravariant. It’s not because you cannot safely assign animals to dogs, as animals may contain non-Dogs. It’s exactly the same as in Tuple’s case. Mypy agrees:

Now, what about the covariance? If List was a covariant type, we could safely use a variable of the type List[Dog] instead of a variable of the type List[Animal], yet we cannot:

Why? Shouldn’t it be the same as in Tuple’s case as well?

Let’s step back a little and think what the difference between covariant Tuple type and List type is. Both are Sized, both are Iterables and both are Containers. Yet, there is an essential difference between lists and tuples — mutability. Python tuples are immutable — you cannot add or remove their elements. Lists are mutable — you can add and remove their elements. It turns out that List’s mutability is something that determines List type not being covariant. If we used List[Dog] wherever List[Animal] is expected, we could append an incompatible object:

So dogs list of the type List[Dog] got an object that cannot bark — a Kangaroo. That’s why you cannot safely use object of List[Dog] type whenever there is an object of the type List[Animal] expected. Therefore List[Dog] is not a subtype of List[Animal]. Remember: the type is defined not only by a set of objects but also by functions/methods that can be used with these objects.

This is the same exploit that we discovered when discussing Callable. But List, contrary to Callable, is not contravariant either, as we've seen. It is invariant then:

We neither have that List[SubType] <: List[SuperType] nor that List[SuperType] <: List[SubType], for SubType <: SuperType.

Other invariant types are Set, Dict, and many more mutable containers. I think it is pretty obvious now and no further examples are needed. This feature of immutable containers is clearly advantageous over mutable ones. But that’s another story for another time…

In more general terms, any structure that supports both read and write operations on some set of objects — mutable container, queue, stack, heap, router, etc. — is invariant in the type of the objects it operates on.

Bonus: Liskov Substitution Principle

In this blog post series, I frequently said something like it’s type-safe to use an object of the SubType type where an object of the SuperType type is expected. This assumption is based on Liskov Substitution Principle — the principle formulated by Barbara Liskov, an American computer scientist. Wikipedia states it as follows:

[…] if S is a subtype of T, then objects of type T may be replaced with objects of type S (i.e. an object of type T may be substituted with any object of a subtype S) without altering any of the desirable properties of the program (correctness, task performed, etc.). [source]

This is a pretty strong requirement — when I replace any object of SuperType with an object of SubType (where SubType <: SuperType) my program still needs to function correctly. It means not only that it cannot raise any new exceptions, but also it still needs to work according to its (original) specification. This even means that we cannot override methods in subclasses if it changes the original behaviour; we can only add new methods. Python type system is not so rigid and mypy won’t complain when we override a method and change its behaviour (both methods— overridden and overriding — still need to have the same argument types, though!). Yet, it’s good to know how to write even safer code 👷

If you want to know more on this topic I suggest reading Liskov and type safety blog post by Brent Roose.