Covariance, Invariance and Contravariance Explained in Plain English

Covariance, Invariance and Contravariance explained in plain English?

Some say it is about relationship between types and subtypes, other say it is about type conversion and others say it is used to decide whether a method is overwritten or overloaded.

All of the above.

At heart, these terms describe how the subtype relation is affected by type transformations. That is, if A and B are types, f is a type transformation, and ≤ the subtype relation (i.e. A ≤ B means that A is a subtype of B), we have

f is covariant if A ≤ B implies that f(A) ≤ f(B)
f is contravariant if A ≤ B implies that f(B) ≤ f(A)
f is invariant if neither of the above holds

Let's consider an example. Let f(A) = List<A> where List is declared by

class List<T> { ... }

Is f covariant, contravariant, or invariant? Covariant would mean that a List<String> is a subtype of List<Object>, contravariant that a List<Object> is a subtype of List<String> and invariant that neither is a subtype of the other, i.e. List<String> and List<Object> are inconvertible types. In Java, the latter is true, we say (somewhat informally) that generics are invariant.

Another example. Let f(A) = A[]. Is f covariant, contravariant, or invariant? That is, is String[] a subtype of Object[], Object[] a subtype of String[], or is neither a subtype of the other? (Answer: In Java, arrays are covariant)

This was still rather abstract. To make it more concrete, let's look at which operations in Java are defined in terms of the subtype relation. The simplest example is assignment. The statement

x = y;

will compile only if typeof(y) ≤ typeof(x). That is, we have just learned that the statements

ArrayList<String> strings = new ArrayList<Object>();
ArrayList<Object> objects = new ArrayList<String>();

will not compile in Java, but

Object[] objects = new String[1];

will.

Another example where the subtype relation matters is a method invocation expression:

result = method(a);

Informally speaking, this statement is evaluated by assigning the value of a to the method's first parameter, then executing the body of the method, and then assigning the methods return value to result. Like the plain assignment in the last example, the "right hand side" must be a subtype of the "left hand side", i.e. this statement can only be valid if typeof(a) ≤ typeof(parameter(method)) and returntype(method) ≤ typeof(result). That is, if method is declared by:

Number[] method(ArrayList<Number> list) { ... }

none of the following expressions will compile:

Integer[] result = method(new ArrayList<Integer>());
Number[] result = method(new ArrayList<Integer>());
Object[] result = method(new ArrayList<Object>());

but

Number[] result = method(new ArrayList<Number>());
Object[] result = method(new ArrayList<Number>());

will.

Another example where subtyping matters is overriding. Consider:

Super sup = new Sub();
Number n = sup.method(1);

where

class Super {
    Number method(Number n) { ... }
}

class Sub extends Super {
    @Override 
    Number method(Number n);
}

Informally, the runtime will rewrite this to:

class Super {
    Number method(Number n) {
        if (this instanceof Sub) {
            return ((Sub) this).method(n);  // *
        } else {
            ... 
        }
    }
}

For the marked line to compile, the method parameter of the overriding method must be a supertype of the method parameter of the overridden method, and the return type a subtype of the overridden method's one. Formally speaking, f(A) = parametertype(method asdeclaredin(A)) must at least be contravariant, and if f(A) = returntype(method asdeclaredin(A)) must at least be covariant.

Note the "at least" above. Those are minimum requirements any reasonable statically type safe object oriented programming language will enforce, but a programming language may elect to be more strict. In the case of Java 1.4, parameter types and method return types must be identical (except for type erasure) when overriding methods, i.e. parametertype(method asdeclaredin(A)) = parametertype(method asdeclaredin(B)) when overriding. Since Java 1.5, covariant return types are permitted when overriding, i.e. the following will compile in Java 1.5, but not in Java 1.4:

class Collection {
    Iterator iterator() { ... }
}

class List extends Collection {
    @Override 
    ListIterator iterator() { ... }
}

I hope I covered everything - or rather, scratched the surface. Still I hope it will help to understand the abstract, but important concept of type variance.

Difference between Variance, Covariance, Contravariance and Bivariance in TypeScript

Variance has to do with how a generic type F<T> varies with respect to its type parameter T. If you know that T extends U, then variance will tell you whether you can conclude that F<T> extends F<U>, conclude that F<U> extends F<T>, or neither, or both.

Covariance means that F<T> and T co-vary. That is, F<T> varies with (in the same direction as) T. In other words, if T extends U, then F<T> extends F<U>. Example:

Function or method types co-vary with their return types:

type Co<V> = () => V;
function covariance<U, T extends U>(t: T, u: U, coT: Co<T>, coU: Co<U>) {
  u = t; // okay
  t = u; // error!

  coU = coT; // okay
  coT = coU; // error!
}

Other (un-illustrated for now) examples are:

objects are covariant in their property types, even though this not sound for mutable properties
class constructors are covariant in their instance types

Contravariance means that F<T> and T contra-vary. That is, F<T> varies counter to (in the opposite direction from) T. In other words, if T extends U, then F<U> extends F<T>. Example:

Function types contra-vary with their parameter types (with --strictFunctionTypes enabled):

type Contra<V> = (v: V) => void;
function contravariance<U, T extends U>(t: T, u: U, contraT: Contra<T>, contraU: Contra<U>) {
  u = t; // okay
  t = u; // error!

  contraU = contraT; // error!
  contraT = contraU; // okay
}

Other (un-illustrated for now) examples are:

objects are contravariant in their key types
class constructors are contravariant in their construct parameter types

Invariance means that F<T> neither varies with nor against T: F<T> is neither covariant nor contravariant in T. This is actually what happens in the most general case. Covariance and contravariance are "fragile" in that when you combine covariant and contravariant type functions, its easy to produce invariant results. Example:

Function types that return the same type as their parameter neither co-vary nor contra-vary in that type:

type In<V> = (v: V) => V;
function invariance<U, T extends U>(t: T, u: U, inT: In<T>, inU: In<U>) {
  u = t; // okay
  t = u; // error!

  inU = inT; // error!
  inT = inU; // error!
}

Bivariance means that F<T> varies both with and against T: F<T> is both covariant nor contravariant in T. In a sound type system, this essentially never happens for any non-trivial type function. You can demonstrate that only a constant type function like type F<T> = string is truly bivariant (quick sketch: T extends unknown is true for all T, so F<T> extends F<unknown> and F<unknown> extends T, and in a sound type system if A extends B and B extends A, then A is the same as B. So if F<T> = F<unknown> for all T, then F<T> is constant).

But Typescript does not have nor does it intend to have a fully sound type system. And there is one notable case where TypeScript treats a type function as bivariant:

Method types both co-vary and contra-vary with their parameter types (this also happens with all function types with --strictFunctionTypes disabled):

type Bi<V> = { foo(v: V): void };
function bivariance<U, T extends U>(t: T, u: U, biT: Bi<T>, biU: Bi<U>) {
  u = t; // okay
  t = u; // error!

  biU = biT; // okay
  biT = biU; // okay
}

Playground link to code

Invariance, covariance and contravariance in Java

This is not specific to OO, but has to do with the properties of certain types.

For example, with the function type

 A -> B                 // functional notation
 public B meth(A arg)   // how this looks in Java

we have the following:

Let C be a subtype of A, and D be a subtype of B. Then the following is valid:

 B b       = meth(new C());  // B >= B, C < A
 Object o  = meth(new C());  // Object > B, C < A

but the follwoing are invalid:

 D d       = meth(new A());        // because D < B
 B b       = meth(new Object());   // because Object > A

hence, to check whether a call of meth is valid, we must check

The expected return type is a supertype of the declared return type.
The actual argument type is a subtype of the declared argument type.

This is all well known and intuitive. By convention we say that the return type of a function is covariant, and the argument type of a method is contravariant.

With parameterized types, like List, we have it that the argument type is invariant in languages like Java, where we have mutability. We can't say that a list of C's is a list of A's, because, if it were so, we could store an A in a list of Cs, much to the surprise of the caller, who assumes only Cs in the list. However, in languages where values are immutable, like Haskell, this is not a problem. Because the data we pass to functions cannot be mutated, a list of C actually is a list of A if C is a subtype of A. (Note that Haskell has no real subtyping, but has instead the related notion of "more/less polymorphic" types.)

still confused about covariance and contravariance & in/out

Both covariance and contravariance in C# 4.0 refer to the ability of using a derived class instead of base class. The in/out keywords are compiler hints to indicate whether or not the type parameters will be used for input and output.

Covariance

Covariance in C# 4.0 is aided by out keyword and it means that a generic type using a derived class of the out type parameter is OK. Hence

IEnumerable<Fruit> fruit = new List<Apple>();

Since Apple is a Fruit, List<Apple> can be safely used as IEnumerable<Fruit>

Contravariance

Contravariance is the in keyword and it denotes input types, usually in delegates. The principle is the same, it means that the delegate can accept more derived class.

public delegate void Func<in T>(T param);

This means that if we have a Func<Fruit>, it can be converted to Func<Apple>.

Func<Fruit> fruitFunc = (fruit)=>{};
Func<Apple> appleFunc = fruitFunc;

Why are they called co/contravariance if they are basically the same thing?

Because even though the principle is the same, safe casting from derived to base, when used on the input types, we can safely cast a less derived type (Func<Fruit>) to a more derived type (Func<Apple>), which makes sense, since any function that takes Fruit, can also take Apple.

Difference between Covariance & Contra-variance

The question is "what is the difference between covariance and contravariance?"

Covariance and contravariance are properties of a mapping function that associates one member of a set with another. More specifically, a mapping can be covariant or contravariant with respect to a relation on that set.

Consider the following two subsets of the set of all C# types. First:

{ Animal, 
  Tiger, 
  Fruit, 
  Banana }.

And second, this clearly related set:

{ IEnumerable<Animal>, 
  IEnumerable<Tiger>, 
  IEnumerable<Fruit>, 
  IEnumerable<Banana> }

There is a mapping operation from the first set to the second set. That is, for each T in the first set, the corresponding type in the second set is IEnumerable<T>. Or, in short form, the mapping is T → IE<T>. Notice that this is a "thin arrow".

With me so far?

Now let's consider a relation. There is an assignment compatibility relationship between pairs of types in the first set. A value of type Tiger can be assigned to a variable of type Animal, so these types are said to be "assignment compatible". Let's write "a value of type X can be assigned to a variable of type Y" in a shorter form: X ⇒ Y. Notice that this is a "fat arrow".

So in our first subset, here are all the assignment compatibility relationships:

Tiger  ⇒ Tiger
Tiger  ⇒ Animal
Animal ⇒ Animal
Banana ⇒ Banana
Banana ⇒ Fruit
Fruit  ⇒ Fruit

In C# 4, which supports covariant assignment compatibility of certain interfaces, there is an assignment compatibility relationship between pairs of types in the second set:

IE<Tiger>  ⇒ IE<Tiger>
IE<Tiger>  ⇒ IE<Animal>
IE<Animal> ⇒ IE<Animal>
IE<Banana> ⇒ IE<Banana>
IE<Banana> ⇒ IE<Fruit>
IE<Fruit>  ⇒ IE<Fruit>

Notice that the mapping T → IE<T> preserves the existence and direction of assignment compatibility. That is, if X ⇒ Y, then it is also true that IE<X> ⇒ IE<Y>.

If we have two things on either side of a fat arrow, then we can replace both sides with something on the right hand side of a corresponding thin arrow.

A mapping which has this property with respect to a particular relation is called a "covariant mapping". This should make sense: a sequence of Tigers can be used where a sequence of Animals is needed, but the opposite is not true. A sequence of animals cannot necessarily be used where a sequence of Tigers is needed.

That's covariance. Now consider this subset of the set of all types:

{ IComparable<Tiger>, 
  IComparable<Animal>, 
  IComparable<Fruit>, 
  IComparable<Banana> }

now we have the mapping from the first set to the third set T → IC<T>.

In C# 4:

IC<Tiger>  ⇒ IC<Tiger>
IC<Animal> ⇒ IC<Tiger>     Backwards!
IC<Animal> ⇒ IC<Animal>
IC<Banana> ⇒ IC<Banana>
IC<Fruit>  ⇒ IC<Banana>     Backwards!
IC<Fruit>  ⇒ IC<Fruit>

That is, the mapping T → IC<T> has preserved the existence but reversed the direction of assignment compatibility. That is, if X ⇒ Y, then IC<X> ⇐ IC<Y>.

A mapping which preserves but reverses a relation is called a contravariant mapping.

Again, this should be clearly correct. A device which can compare two Animals can also compare two Tigers, but a device which can compare two Tigers cannot necessarily compare any two Animals.

So that's the difference between covariance and contravariance in C# 4. Covariance preserves the direction of assignability. Contravariance reverses it.

What is the difference between covariance and contra-variance in programming languages?

Covariance is pretty simple and best thought of from the perspective of some collection class List. We can parameterize the List class with some type parameter T. That is, our list contains elements of type T for some T. List would be covariant if

S is a subtype of T iff List[S] is a subtype of List[T]

(Where I'm using the mathematical definition iff to mean if and only if.)

That is, a List[Apple] is a List[Fruit]. If there is some routine which accepts a List[Fruit] as a parameter, and I have a List[Apple], then I can pass this in as a valid parameter.

def something(l: List[Fruit]) {
    l.add(new Pear())
}

If our collection class List is mutable, then covariance makes no sense because we might assume that our routine could add some other fruit (which was not an apple) as above. Hence we should only like immutable collection classes to be covariant!

Contravariance explained

Update: Ooops. As it turned out, I mixed up variance and "assignment compatibility" in my initial answer. Edited the answer accordingly. Also I wrote a blog post that I hope should answer such questions better: Covariance and Contravariance FAQ

Answer: I guess the answer to your first question is that you don't have contravariance in this example:

bool Compare(Mammal mammal1, Mammal mammal2); 
Mammal mammal1 = new Giraffe(); //covariant - no             
Mammal mammal2 = new Dolphin(); //covariant - no            

Compare(mammal1, mammal2); //covariant or contravariant? - neither            
//or             
Compare(new Giraffe(), new Dolphin()); //covariant or contravariant? - neither

Furthermore, you don't even have covariance here. What you have is called "assignment compatibility", which means that you can always assign an instance of a more derived type to an instance of a less derived type.

In C#, variance is supported for arrays, delegates, and generic interfaces. As Eric Lippert said in his blog post What's the difference between covariance and assignment compatibility? is that it's better to think about variance as "projection" of types.

Covariance is easier to understand, because it follows the assignment compatibility rules (array of a more derived type can be assigned to an array of a less derived type, "object[] objs = new string[10];"). Contravariance reverses these rules. For example, imagine that you could do something like "string[] strings = new object[10];". Of course, you can't do this because of obvious reasons. But that would be contravariance (but again, arrays are not contravariant, they support covariance only).

Here are the examples from MSDN that I hope will show you what contravariance really means (I own these documents now, so if you think something is unclear in the docs, feel free to give me feedback):

Using Variance in Interfaces for Generic Collections

Employee[] employees = new Employee[3];
// You can pass PersonComparer, 
// which implements IEqualityComparer<Person>,
// although the method expects IEqualityComparer<Employee>.
IEnumerable<Employee> noduplicates =
    employees.Distinct<Employee>(new PersonComparer());

Using Variance in Delegates

// Event hander that accepts a parameter of the EventArgs type.
private void MultiHandler(object sender, System.EventArgs e)
{
   label1.Text = System.DateTime.Now.ToString();
}
public Form1()
{
    InitializeComponent();
    // You can use a method that has an EventArgs parameter,
    // although the event expects the KeyEventArgs parameter.
    this.button1.KeyDown += this.MultiHandler;
    // You can use the same method 
    // for an event that expects the MouseEventArgs parameter.
    this.button1.MouseClick += this.MultiHandler;
 }

Using Variance for Func and Action Generic Delegates

 static void AddToContacts(Person person)
 {
   // This method adds a Person object
   // to a contact list.
 }

 // The Action delegate expects 
 // a method that has an Employee parameter,
 // but you can assign it a method that has a Person parameter
 // because Employee derives from Person.
 Action<Employee> addEmployeeToContacts = AddToContacts;

Hope this helps.

could someone explain the connection between type covariance/contravariance and category theory?

A contravariant functor from $C$ to $D$ is the exact same thing as a normal (i.e. covariant) functor from $C$ to $D^{op}$, where $D^{op}$ is the opposite category of $D$. So it's probably best to understand opposite categories first -- then you'll automatically understand contravariant functors!

Contravariant functors don't come up all that often in CS, although I can think of two exceptions:

You may have heard of contravariance in the context of subtyping. Although this is technically the same term, the connection is really, really weak. In object oriented programming, the classes form a partial order; every partial order is a category with "binary hom-sets" -- given any two objects $A$ and $B$, there is exactly one morphism $A\to B$ iff $A\leq B$ (note the direction; this slightly-confusing orientation is the standard for reasons I won't explain here) and no morphisms otherwise.
Parameterized types like, say, Scala's PartialFunction[-A,Unit] are functors from this simple category to itself... we usually focus on what they do to objects: given a class X, PartialFunction[X,Unit] is also a class. But functors preserve morphisms too; in this case if we had a subclass Dog of Animal, we would have a morphism Dog$\to$Animal, and the functor would preserve this morphism, giving us a morphism PartialFunction[Animal,Unit]$\to$PartialFunction[Dog,Unit], telling us that PartialFunction[Animal,Unit] is a subclass of PartialFunction[Dog,Unit]. If you think about that, it makes sense: suppose you have a situation where you need a function that works on Dogs. A function that works on all Animals would certainly work there!
That said, using full-on category theory to talk about partially ordered sets is big-time overkill.
Less common, but actually uses the category theory: consider the category Types(Hask) whose objects are the types of the Haskell programming language and where a morphism $\tau_1\to\tau_2$ is a function of type $\tau_1$->$\tau_2$. There is also a category Judgments(Hask) whose objects are lists of typing judgments $\tau_1\vdash\tau_2$ and whose morphisms are proofs of all the judgments on one list using the judgments on the other list as hypotheses. There is a functor from Types(Hask) to Judgments(Hask) which takes a Types(Hask)-morphism $f:A\to B$ to the proof


     B |- Int
    ----------
      ......
    ----------
     A |- Int

which is a morphism $(B\vdash Int)\to(A\vdash Int)$ -- notice the change of direction. Basically what this is saying is that if you've got a function that turns A's into B'a, and an expression of type Int with a free variable x of type B, then you can wrap it with "let x = f y in ..." and arrive at an expression still of type Int but whose only free variable is of type $A$, not $B$.

C# : Is Variance (Covariance / Contravariance) another word for Polymorphism?

It's certainly related to polymorphism. I wouldn't say they're just "another word" for polymorphism though - they're about very specific situations, where you can treat one type as if it were another type in a certain context.

For instance, with normal polymorphism you can treat any reference to a Banana as a reference to a Fruit - but that doesn't mean you can substitute Fruit every time you see the type Banana. For example, a List<Banana> can't be treated as a List<Fruit> because list.Add(new Apple()) is valid for List<Fruit> but not for List<Banana>.

Covariance allows a "bigger" (less specific) type to be substituted in an API where the original type is only used in an "output" position (e.g. as a return value). Contravariance allows a "smaller" (more specific) type to be substituted in an API where the original type is only used in an "input" position.

It's hard to go into all the details in a single SO post (although hopefully someone else will do a better job than this!). Eric Lippert has an excellent series of blog posts about it.

Covariance, Invariance and Contravariance Explained in Plain English