In computer programming, type variance is the relationship between subtypes of a composite type (e.g. List[Int]) and the subtypes of its components (e.g. Int). A language's chosen variance determines the relationship between, for example, a list of Cats and a list of Animals, or a function returning Cat and a function returning Animal. If the type Cat is a subtype of Animal, then an expression of type Cat should be substitutable wherever an expression of type Animal is used. 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 many programming languages, for example, "list of Cat" will be 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.
Etymology
These terms come from the notion of covariant and contravariant functors in category theory. Consider the category C {\displaystyle C} whose objects are types and whose morphisms represent the subtype relationship ≤. (This is an example of how any partially ordered set can be considered as a category.) Then for example the function type constructor takes two types p and r and creates a new type p → r; so it takes objects in C 2 {\displaystyle C^{2}} to objects in C {\displaystyle C} . By the subtyping rule for function types this operation reverses ≤ for the first parameter and preserves it for the second, so it is a contravariant functor in the first parameter and a covariant functor in the second.
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 Cat is a subtype of Animal, then:
IEnumerable<Cat> is a subtype of IEnumerable<Animal>. The subtyping is preserved because IEnumerable<T> is covariant on T. Action<Animal> is a subtype of Action<Cat>. The subtyping is reversed because Action<T> is contravariant on T. Neither IList<Cat> nor IList<Animal> is a subtype of the other, because IList<T> is invariant on T. The variance of a C# generic interface is declared by placing the out (covariant) or in (contravariant) attribute on (zero or more of) its type parameters. The above interfaces are declared as IEnumerable<out T>, Action<in T>, and IList<T>. Types with more than one type parameter may specify different variances on each type parameter. For example, the delegate type Func<in T, out TResult> represents a function with a contravariant input parameter of type T and a covariant return value of type TResult. 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 Action<T> represents a first-class function expecting an argument of type T, 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 Animal we can make the type Animal[], 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 Cat[] is an Animal[]; contravariant: an Animal[] is a Cat[]; invariant: an Animal[] is not a Cat[] and a Cat[] is not an Animal[]. If we wish to avoid type errors, then only the third choice is safe. Clearly, not every Animal[] can be treated as if it were a Cat[], since a client reading from the array will expect a Cat, but an Animal[] may contain e.g. a Dog. So, the contravariant rule is not safe. Conversely, a Cat[] cannot be treated as an Animal[]. It should always be possible to put a Dog into an Animal[]. With covariant arrays this cannot be guaranteed to be safe, since the backing store might actually be an array of cats. So, the covariant rule is also not safe—the array constructor should be invariant. Note that this is only an issue for mutable arrays; the covariant rule is safe for immutable (read-only) arrays. Likewise, the contravariant rule would be safe for write-only arrays.
… excerpt ends here. Continue reading the full article.
