Covariance and contravariance (computer science)

Many programming language type systems support subtyping. For instance, if the type is a subtype of , then an expression of type should be substitutable wherever an expression of type is used.

Variance is how subtyping between more complex types relates to subtyping between their components. For example, how should a list of s relate to a list of s? Or how should a function that returns relate to a function that returns ?

Depending on the variance of the type constructor, the subtyping relation of the simple types may be either preserved, reversed, or ignored for the respective complex types. In the OCaml programming language, for example, "list of Cat" is a subtype of "list of Animal" because the list type constructor is covariant. This means that the subtyping relation of the simple types is preserved for the complex types.

On the other hand, "function from Animal to String" is a subtype of "function from Cat to String" because the function type constructor is contravariant in the parameter type. Here, the subtyping relation of the simple types is reversed for the complex types.

A programming language designer will consider variance when devising typing rules for language features such as arrays, inheritance, and generic datatypes. By making type constructors covariant or contravariant instead of invariant, more programs will be accepted as well-typed. On the other hand, programmers often find contravariance unintuitive, and accurately tracking variance to avoid runtime type errors can lead to complex typing rules.

In order to keep the type system simple and allow useful programs, a language may treat a type constructor as invariant even if it would be safe to consider it variant, or treat it as covariant even though that could violate type safety.

Formal definition

Suppose A and B are types, and I<U> denotes application of a type constructor I with type argument U. Within the type system of a programming language, a typing rule for a type constructor I is: covariant if it preserves the ordering of types (≤), which orders types from more specific to more generic: If A ≤ B, then I<A> ≤ I<B>; contravariant if it reverses this ordering: If A ≤ B, then I<B> ≤ I<A>; bivariant if both of these apply (i.e., if A ≤ B, then I<A> ≡ I<B>); variant if covariant, contravariant or bivariant; invariant or nonvariant if not variant.

The article considers how this applies to some common type constructors.

C# examples

For example, in C#, if is a subtype of , then: is a subtype of . The subtyping is preserved because is covariant on . is a subtype of . The subtyping is reversed because is contravariant on . Neither nor is a subtype of the other, because is invariant on . The variance of a C# generic interface is declared by placing the (covariant) or (contravariant) attribute on (zero or more of) its type parameters. The above interfaces are declared as , , and . Types with more than one type parameter may specify different variances on each type parameter. For example, the delegate type represents a function with a contravariant input parameter of type and a covariant return value of type . The compiler checks that all types are defined and used consistently with their annotations, and otherwise signals a compilation error.

The typing rules for interface variance ensure type safety. For example, an represents a first-class function expecting an argument of type , and a function that can handle any type of animal can always be used instead of one that can only handle cats.

Arrays

Read-only data types (sources) can be covariant; write-only data types (sinks) can be contravariant. Mutable data types which act as both sources and sinks should be invariant. To illustrate this general phenomenon, consider the array type. For the type we can make the type , which is an "array of animals". For the purposes of this example, this array supports both reading and writing elements.

We have the option to treat this as either: covariant: a is an ; contravariant: an is a ; invariant: an is not a and a is not an .

If we wish to avoid type errors, then only the third choice is safe. Clearly, not every can be treated as if it were a , since a client reading from the array will expect a , but an may contain e.g. a . So the contravariant rule is not safe.