Difference Between Covariance & Contra-Variance

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!

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

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.

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.

Difference between covariant and contravariant positions in Typescript

Your observation that one of the examples resolves to never is accurate and you are not missing any compiler settings. In newer versions of TS, intersections of primitive types resolve to never. If you revert to an older version you will still see string & number. In newer version you can still see the contravariant position behavior if you use object types:

type Bar<T> = T extends { a: (x: infer U) => void, b: (x: infer U) => void } ? U : never;
type T21 = Bar<{ a: (x: { h: string }) => void, b: (x: { g: number }) => void }>;  // {h: string; } & { g: number;}

Playground Link

As to why are function parameters contravariant while properties are covariant, it's a tradeoff between type safety and usability.

For function arguments, it is easy to see why they would be contravariant. You can only call a function safely with a subtype of the argument, not a base type.

class Animal { eat() { } }
class Dog extends Animal { wof() { } }

type Fn<T> = (p: T) => void
var contraAnimal: Fn<Animal> = a => a.eat();
var contraDog: Fn<Dog> = d => { d.eat(); d.wof() }
contraDog(new Animal()) // error, d.wof would fail 
contraAnimal = contraDog; // so this also fails

contraAnimal(new Dog()) // This is ok
contraDog = contraAnimal; // so this is also ok

Playground Link

Since Fn<Animal> and Fn<Dog> are assignable in the opposite direction as two variables of types Dog and Animal would be, the function parameter position makes Fn contravariant in T

For properties, the discussion as to why they are covariant is a bit more complicated. The TL/DR is that a field position (ex { a: T }) would make the type actually invariant, but that would make life hard so in TS, by definition a field type position (such as T has above) makes the type covariant in that field type( so { a: T } is covariant in T). We could demonstrate that for the a is read-only case, { a: T } would covariant, and for the a is write-only case { a: T } would be contravariant, and both cases together give us invariance, but I'm not sure that is strictly necessary, instead, I leave you with this example of where this covariant by default behavior can lead to correctly typed code having runtime errors:

type SomeType<T> = { a: T }

function foo(a: SomeType<{ foo: string }>) {
    a.a = { foo: "" } // no bar here, not needed
}
let b: SomeType<{ foo: string, bar: number }> = {
    a: { foo: "", bar: 1 }
}

foo(b) // valid T is in a covariant position, so SomeType<{ foo: string, bar: number }> is assignable to SomeType<{ foo: string }>
b.a.bar.toExponential() // Runtime error nobody in foo assigned bar

Playground Link

You might also find this post of mine on variance in TS interesting.

Covariance and Contravariance - Just different mechanisms for invoking guaranteed base class behavior?

I'm having a struggle understanding these two concepts.

Yes you are. Many people do.

But I think after many videos and SO QA's, I have it distilled down to its simplest form:

You have not.

Covariance means that a sub-type can do what its base-type does.

No. That's the Liskov Substitution Principle.

Contravariance means you can treat a sub-type the same way you would treat its base-type.

No. That's just re-stating what you said for covariance.

The real distillation of covariance and contravariance is:

A covariant conversion preserves the direction of another conversion.
A contravariant conversion reverses the direction of another conversion.

Dog is convertible to Animal. IEnumerable<Dog> is convertible to IEnumerable<Animal>.
The direction is preserved, so IEnumerable<T> is covariant. IComparable<Animal> is convertible to IComparable<Dog>, which reverses the direction of the conversion, so it is contravariant.

I understand mathematically what covariance means, and so I guess it's the same in compsci.

Just to be clear: mathematicians use "variance" to mean a bunch of different things. The meaning that is common to mathematics and computer science is the category theory definition.

In C# it's just a matter of where and in what ways these two types of relationships are supported?

Mathematically, variance tells you about whether a relation is preserved or reversed by a mapping. If we have the mapping T --> IEnumerable<T> and the relation "is convertible to via identity or reference conversion" then it is the case that in C#, if X relates to Y then IE<X> relates to IE<Y>. The mapping is therefore said to be covariant with respect to the relation.

what is it that these features are trying to accomplish by supporting them?

People frequently requested "I have a method that takes a sequence of animals and I have a sequence of turtles in hand; why do I have to copy the sequence to a new sequence to use the method?" That's a reasonable request, we got it frequently, and we got it a lot more frequently after LINQ made it easier to work with sequences. It's a generally useful feature that we could implement at a reasonable cost, so we implemented it.

Covariance and contravariance real world example

Let's say you have a class Person and a class that derives from it, Teacher. You have some operations that take an IEnumerable<Person> as the argument. In your School class you have a method that returns an IEnumerable<Teacher>. Covariance allows you to directly use that result for the methods that take an IEnumerable<Person>, substituting a more derived type for a less derived (more generic) type. Contravariance, counter-intuitively, allows you to use a more generic type, where a more derived type is specified.

See also Covariance and Contravariance in Generics on MSDN.

Classes:

public class Person 
{
     public string Name { get; set; }
} 

public class Teacher : Person { } 

public class MailingList
{
    public void Add(IEnumerable<out Person> people) { ... }
}

public class School
{
    public IEnumerable<Teacher> GetTeachers() { ... }
}

public class PersonNameComparer : IComparer<Person>
{
    public int Compare(Person a, Person b) 
    { 
        if (a == null) return b == null ? 0 : -1;
        return b == null ? 1 : Compare(a,b);
    }

    private int Compare(string a, string b)
    {
        if (a == null) return b == null ? 0 : -1;
        return b == null ? 1 : a.CompareTo(b);
    }
}

Usage:

var teachers = school.GetTeachers();
var mailingList = new MailingList();

// Add() is covariant, we can use a more derived type
mailingList.Add(teachers);

// the Set<T> constructor uses a contravariant interface, IComparer<in T>,
// we can use a more generic type than required.
// See https://msdn.microsoft.com/en-us/library/8ehhxeaf.aspx for declaration syntax
var teacherSet = new SortedSet<Teachers>(teachers, new PersonNameComparer());

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 Covariance & Contra-Variance