Contravariance Explained

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.

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.

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 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.

C# dont understand covariance and contravariance of delegates

Following the comments under the question, the Variance in Delegates document will explain that

.NET Framework 3.5 introduced variance support for matching method
signatures with delegate types in all delegates in C#. This means that
you can assign to delegates not only methods that have matching
signatures, but also methods that return more derived types
(covariance) or that accept parameters that have less derived types
(contravariance) than that specified by the delegate type.

So, your assignment MyDelegate<Dog, Mammal> myDelegate = TestMethod; is perfectly fine, despite different signatures on delegate and TestMethod (reversed input parameter and return type).

But in and out parameters are still needed when you have an implicit conversion between delegates, according to Variance in Generic Type Parameters section

To enable implicit conversion, you must explicitly declare generic
parameters in a delegate as covariant or contravariant by using the in
or out keyword.

E.g. the following code will not compile

MyDelegate<Dog, Mammal> myDelegate = TestMethod;
MyDelegate<Dog, Dog> anotherDelegate = TestMethod;
myDelegate = anotherDelegate; //error CS0029: Cannot implicitly convert type...

Until you declare MyDelegate witn contravariant parameter and covariant return type

delegate TOut MyDelegate<in TIn, out TOut>(TIn input);

After that last line will compile

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.

Problem understanding covariance contravariance with generics in C#

The error message is insufficiently informative, and that is my fault. Sorry about that.

The problem you are experiencing is a consequence of the fact that covariance only works on reference types.

You're probably saying "but IA is a reference type" right now. Yes, it is. But you didn't say that T is equal to IA. You said that T is a type which implements IA, and a value type can implement an interface. Therefore we do not know whether covariance will work, and we disallow it.

If you want covariance to work you have to tell the compiler that the type parameter is a reference type with the class constraint as well as the IA interface constraint.

The error message really should say that the conversion is not possible because covariance requires a guarantee of reference-type-ness, since that is the fundamental problem.

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

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.

Contravariance Explained