{
  "id": "enwiki-001363294136",
  "slug": "type-variance",
  "title": "Type variance",
  "qid": "",
  "lead": "In computer programming, type variance is the relationship between subtypes of a composite type (e.g. ) and the subtypes of its components (e.g. ). A language's chosen variance determines the relationship between, for example, a list of s and a list of s, or a function returning and a function returning . If the type is a subtype of , then an expression of type should be substitutable wherever an expression of type 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.…",
  "body": "In computer programming, type variance is the relationship between subtypes of a composite type (e.g. ) and the subtypes of its components (e.g. ). A language's chosen variance determines the relationship between, for example, a list of s and a list of s, or a function returning and a function returning . If the type is a subtype of , then an expression of type should be substitutable wherever an expression of type 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. boolean equalArrays(Object[] a1, Object[] a2); void shuffleArray(Object[] a); However, if array types were treated as invariant, it would only be possible to call these functions on an array of exactly the type . One could not, for example, shuffle an array of strings. Therefore, both Java and C# treat array types covariantly. For instance, in Java is a subtype of , and in C# is a subtype of . As discussed above, covariant arrays lead to problems with writes into the array. Java and C# deal with this by marking each array object with a type when it is created. Each time a value is stored into an array, the execution environment will check that the run-time type of the value is equal to the run-time type of the array. If there is a mismatch, an (Java) or (C#) is thrown: // a is a single-element array of String String[] a = new String[1]; // b is an array of Object Object[] b = a; // Assign an Integer (int) to b. This would be possible if b were actually // an array of Object, but since it really is an array of String, // we will get a java.lang.ArrayStoreException at runtime. b[0] = 1; In the above example, one can read from the array (b) safely. It is only trying to write to the array that can lead to trouble. One drawback to this approach is that it leaves the possibility of a run-time error that a stricter type system could have caught at compile-time. Also, it hurts performance because each write into an array requires an additional run-time check. With the addition of generics, Java and C# now offer ways to write this kind of polymorphic function without relying on covariance. The array comparison and shuffling functions can be given the parameterized types boolean equalArrays(T[] a1, T[] a2); void shuffleArray(T[] a); Alternatively, to enforce that a C# method accesses a collection in a read-only way, one can use the interface instead of passing it an array . Image:Vererbung T.svg|Subtyping of the parameter/return type of the method. Image:Inheritance_invariant.svg|Invariance. The signature of the overriding method is unchanged. Image:Inheritance_covariant_return.svg|Covariant return type. The subtyping relation is in the same direction as the relation between ClassA and ClassB. Image:Inheritance_contravariant_argument.svg|Contravariant parameter type. The subtyping relation is in the opposite direction to the relation between ClassA and ClassB. Image:Inheritance_covariant_argument.svg|Covariant parameter type. Not type safe. For a concrete example, suppose we are writing a class to model an animal shelter. We assume that is a subclass of , and that we have a base class (using Java syntax) class AnimalShelter { Animal getAnimalForAdoption() { // ... } void putAnimal(Animal animal) { //... } } Now the question is: if we subclass , what types are we allowed to give to and ? class CatShelter extends AnimalShelter { Cat getAnimalForAdoption() { return new Cat(); } } Among mainstream OOP languages, Java, C++ and C# (as of version 9.0 ) support covariant return types. Adding the covariant return type was one of the first modifications of the C++ language approved by the standards committee in 1998. Scala and D also support covariant return types. class CatShelter extends AnimalShelter { void putAnimal(Object animal) { // ... } } Only a few object-oriented languages actually allow this (for example, Python when typechecked with mypy). C++, Java and most other languages that support overloading and/or shadowing would interpret this as a method with an overloaded or shadowed name. However, Sather supported both covariance and contravariance. Calling convention for overridden methods are covariant with out parameters and return values, and contravariant with normal parameters (with the mode in). class CatShelter extends AnimalShelter { void putAnimal(covariant Cat animal) { // ... } } This is not type safe. By up-casting a to an , one can try to place a dog in a cat shelter. That does not meet parameter restrictions and will result in a runtime error. The lack of type safety (known as the \"catcall problem\" in the Eiffel community, where \"cat\" or \"CAT\" is a Changed Availability or Type) has been a long-standing issue. Over the years, various combinations of global static analysis, local static analysis, and new language features have been proposed to remedy it, and these have been implemented in some Eiffel compilers. Despite the type safety problem, the Eiffel designers consider covariant parameter types crucial for modeling real world requirements. The cat shelter illustrates a common phenomenon: it is a kind of animal shelter but has additional restrictions, and it seems reasonable to use inheritance and restricted parameter types to model this. In proposing this use of inheritance, the Eiffel designers reject the Liskov substitution principle, which states that objects of subclasses should always be less restricted than objects of their superclass. One other instance of a mainstream language allowing covariance in method parameters is PHP in regards to class constructors. In the following example, the __construct() method is accepted, despite the method parameter being covariant to the parent's method parameter. Were this method anything other than __construct(), an error would occur: interface AnimalInterface {} interface DogInterface extends AnimalInterface {} class Dog implements DogInterface {} class Pet { public function __construct(AnimalInterface $animal) {} } class PetDog extends Pet { public function __construct(DogInterface $dog) { parent::__construct($dog); } } Another example where covariant parameters seem helpful is so-called binary methods, i.e. methods where the parameter is expected to be of the same type as the object the method is called on. An example is the method: checks whether comes before or after in some ordering, but the way to compare, say, two rational numbers will be different from the way to compare two strings. Other common examples of binary methods include equality tests, arithmetic operations, and set operations like subset and union. In older versions of Java, the comparison method was specified as an interface : interface Comparable { int compareTo(Object o); } The drawback of this is that the method is specified to take an argument of type . A typical implementation would first down-cast this argument (throwing an error if it is not of the expected type): class RationalNumber implements Comparable { int numerator; int denominator; // ... public int compareTo(Object other) { RationalNumber otherNum = (RationalNumber)other; return Integer.compare(numerator * otherNum.denominator, otherNum.numerator * denominator); } } In a language with covariant parameters, the argument to could be directly given the desired type , hiding the typecast. (Of course, this would still give a runtime error if was then called on e.g. a .) class Shelter { T getAnimalForAdoption() { // ... } void putAnimal(T animal) { // ... } } class CatShelter extends Shelter { Cat getAnimalForAdoption() { // ... } void putAnimal(Cat animal) { // ... } } Similarly, in recent versions of Java the interface has been parameterized, which allows the downcast to be omitted in a type-safe way: class RationalNumber implements Comparable { int numerator; int denominator; // ... public int compareTo(RationalNumber otherNum) { return Integer.compare(numerator * otherNum.denominator, otherNum.numerator * denominator); } } Another language feature that can help is multiple dispatch. One reason that binary methods are awkward to write is that in a call like , selecting the correct implementation of really depends on the runtime type of both and , but in a conventional OO language only the runtime type of is taken into account. In a language with Common Lisp Object System (CLOS)-style multiple dispatch, the comparison method could be written as a generic function where both arguments are used for method selection. Giuseppe Castagna observed that in a typed language with multiple dispatch, a generic function can have some parameters which control dispatch and some \"left-over\" parameters which do not. Because the method selection rule chooses the most specific applicable method, if a method overrides another method, then the overriding method will have more specific types for the controlling parameters. On the other hand, to ensure type safety the language still must require the left-over parameters to be at least as general. Using the previous terminology, types used for runtime method selection are covariant while types not used for runtime method selection of the method are contravariant. Conventional single-dispatch languages like Java also obey this rule: only one argument is used for method selection (the receiver object, passed along to a method as the hidden argument ), and indeed the type of is more specialized inside overriding methods than in the superclass. Castagna suggests that examples where covariant parameter types are superior (particularly, binary methods) should be handled using multiple dispatch; which is naturally covariant. However, most programming languages do not support multiple dispatch. interface IEnumerator { T Current { get; } bool MoveNext(); } With this declaration, will be treated as covariant in its type parameter, e.g. is a subtype of . The type checker enforces that each method declaration in an interface only mentions the type parameters in a way consistent with the / annotations. That is, a parameter that was declared covariant must not occur in any contravariant positions (where a position is contravariant if it occurs under an odd number of contravariant type constructors). The precise rule is that the return types of all methods in the interface must be valid covariantly and all the method parameter types must be valid contravariantly, where valid S-ly is defined as follows: Non-generic types (classes, structs, enums, etc.) are valid both co- and contravariantly. A type parameter is valid covariantly if it was not marked , and valid contravariantly if it was not marked . An array type is valid S-ly if is. (This is because C# has covariant arrays.) A generic type is valid S-ly if for each parameter , Ai is valid S-ly, and the ith parameter to is declared covariant, or Ai is valid (not S)-ly, and the ith parameter to is declared contravariant, or Ai is valid both covariantly and contravariantly, and the ith parameter to is declared invariant. As an example of how these rules apply, consider the interface. interface IList { void Insert(int index, T item); IEnumerator GetEnumerator(); } The parameter type of must be valid contravariantly, i.e. the type parameter must not be tagged . Similarly, the result type of must be valid covariantly, i.e. (since is a covariant interface) the type must be valid covariantly, i.e. the type parameter must not be tagged . This shows that the interface is not allowed to be marked either co- or contravariant. In the common case of a generic data structure such as , these restrictions mean that an parameter can only be used for methods getting data out of the structure, and an parameter can only be used for methods putting data into the structure, hence the choice of keywords. C# allows variance annotations on the parameters of interfaces, but not the parameters of classes. Because fields in C# classes are always mutable, variantly parameterized classes in C# would not be very useful. But languages which emphasize immutable data can make good use of covariant data types. For example, in all of Scala, Kotlin and OCaml the immutable list type is covariant: List[Cat] is a subtype of List[Animal] . Scala's rules for checking variance annotations are essentially the same as C#'s. However, there are some idioms that apply to immutable datastructures in particular. They are illustrated by the following (excerpt from the) definition of the List[A] class. sealed abstract class List[+A] extends AbstractSeq[A] { def head: A def tail: List[A] /** Adds an element at the beginning of this list. */ def ::[B >: A] (x: B): List[B] = new scala.collection.immutable.::(x, this) /** ... */ } First, class members that have a variant type must be immutable. Here, head has the type A , which was declared covariant ( + ), and indeed head was declared as a method ( def ). Trying to declare it as a mutable field ( var ) would be rejected as type error. Second, even if a data structure is immutable, it will often have methods where the parameter type occurs contravariantly. For example, consider the method :: which adds an element to the front of a list. (The implementation works by creating a new object of the similarly named class :: , the class of nonempty lists.) The most obvious type to give it would be def :: (x: A): List[A] However, this would be a type error, because the covariant parameter A appears in a contravariant position (as a function parameter). But there is a trick to get around this problem. We give :: a more general type, which allows adding an element of any type B as long as B is a supertype of A . Note that this relies on List being covariant, since this has type List[A] and we treat it as having type List[B] . At first glance it may not be obvious that the generalized type is sound, but if the programmer starts out with the simpler type declaration, the type errors will point out the place that needs to be generalized. type ('a, 'b) t = T of ('a -> 'b) The compiler will automatically infer that is contravariant in the first parameter, and covariant in the second. The programmer can also provide explicit annotations, which the compiler will check are satisfied. Thus the following declaration is equivalent to the previous one: type (-'a, +'b) t = T of ('a -> 'b) Explicit annotations in OCaml become useful when specifying interfaces. For example, the standard library interface for association tables include an annotation saying that the map type constructor is covariant in the result type. module type S = sig type key type (+'a) t val empty: 'a t val mem: key -> 'a t -> bool ... end This ensures that e.g. is a subtype of . Animal a = l.get(3); because the type is known to be a subtype of , but l.add(new Animal()); will be rejected as a type error since an is not necessarily an . In general, given some interface , a reference to an forbids using methods from the interface where occurs contravariantly in the type of the method. Conversely, if had type one could call but not . While non-wildcard parameterized types in Java are invariant (e.g. there is no subtyping relationship between and ), wildcard types can be made more specific by specifying a tighter bound. For example, is a subtype of . This shows that wildcard types are covariant in their upper bounds (and also contravariant in their lower bounds). In total, given a wildcard type like , there are three ways to form a subtype: by specializing the class , by specifying a tighter bound , or by replacing the wildcard with a specific type (see figure). By applying two of the above three forms of subtyping, it becomes possible to, for example, pass an argument of type to a method expecting a . This is the kind of expressiveness that results from covariant interface types. The type acts as an interface type containing only the covariant methods of , but the implementer of did not have to define it ahead of time. In the common case of a generic data structure , covariant parameters are used for methods getting data out of the structure, and contravariant parameters for methods putting data into the structure. The mnemonic for Producer Extends, Consumer Super (PECS), from the book Effective Java by Joshua Bloch gives an easy way to remember when to use covariance and contravariance. Wildcards are flexible, but there is a drawback. While use-site variance means that API designers need not consider variance of type parameters to interfaces, they must often instead use more complicated method signatures. A common example involves the interface. Suppose we want to write a function that finds the biggest element in a collection. The elements need to implement the method, so a first try might be > T max(Collection coll); However, this type is not general enough&mdash;one can find the max of a , but not a . The problem is that does not implement , but instead the (better) interface . In Java, unlike in C#, is not considered a subtype of . Instead the type of has to be modified: > T max(Collection coll); The bounded wildcard conveys the information that calls only contravariant methods from the interface. This particular example is frustrating because all the methods in are contravariant, so that condition is trivially true. A declaration-site system could handle this example with less clutter by annotating only the definition of . The method can be changed even further by using an upper bounded wildcard for the method parameter: > T max(Collection coll); Covariance and Contravariance - Fabulous Adventures in Coding: An article series about implementation concerns surrounding co/contravariance in C#, by Eric Lippert. (Archived 2008 from MSDN. Some posts are still live on his personal site. More posts in this archive from 2019.) Contra Vs Co Variance (note this article is not updated about C++) Closures for the Java 7 Programming Language (v0.5) The theory behind covariance and contravariance in C# 4",
  "categories": [
    "10639732",
    "106747104",
    "22921787",
    "23118434",
    "23603337",
    "24043274",
    "25911316",
    "26157654",
    "29176688",
    "31128806",
    "57958211",
    "61225812",
    "62213912",
    "7692542",
    "98501778"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1363294136",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1783576226.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001363294136",
    "type": "webpage",
    "title": "Type variance",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/type-variance",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001363294136",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1363294136",
    "note": "Immutable snapshot enwiki-001363294136"
  }
}