C# – Contravariance explained

cc#-4.0contravariancecovariance

First of, I have read many explanations on SO and blogs about covariance and contravariance and a big thanks goes out to Eric Lippert for producing such a great series on Covariance and Contravariance.

However I have a more specific question that I am trying to get my head around a little bit.

As far as I understand per Eric's explanation is that Covariance and Contravariance are both adjectives that describe a transformation. Covariant transformation is that which preserves the order of types and Contravariant transformation is one that reverses it.

I understand covariance in such a manner that I think most developers understand intuitively.

//covariant operation
Animal someAnimal = new Giraffe(); 
//assume returns Mammal, also covariant operation
someAnimal = Mammal.GetSomeMammal();

The return operation here is covariant as we are preserving the size in which both Animal is still bigger than Mammal or Giraffe. On that note most return operations are covariant, contravariant operations would not make sense.

  //if return operations were contravariant
  //the following would be illegal
  //as Mammal would need to be stored in something
  //equal to or less derived than Mammal
  //which would mean that Animal is now less than or equal than Mammal
  //therefore reversing the relationship
  Animal someAnimal =  Mammal.GetSomeMammal();

This piece of code of course would not make sense to most developers.

My confusion lies in Contravariant argument parameters. If you had a method such as

bool Compare(Mammal mammal1, Mammal mammal2);

I have always learned that input parameters always force contravariant behavior. Such that if the type is used as an input parameter its behavior should be contravariant.

However what is the difference between the following code

Mammal mammal1 = new Giraffe(); //covariant
Mammal mammal2 = new Dolphin(); //covariant

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

By the same token that you can't do something like this you can't do

   //not valid
   Mammal mammal1 = new Animal();

   //not valid
   Compare(new Animal(), new Dolphin());

I guess what I am asking is, what makes method argument passing a contravariant transformation.

Sorry for the long post, maybe I am understand this incorrectly.

EDIT:

Per some conversation below, I understand that for instance using a delegate layer can clearly show contravariance. Consider the following example

//legal, covariance
Mammal someMammal = new Mammal();
Animal someAnimal = someMammal;

// legal in C# 4.0, covariance (because defined in Interface)
IEnumerable<Mammal> mammalList = Enumerable.Empty<Mammal>();
IEnumerable<Animal> animalList = mammalList;

//because of this, one would assume
//that the following line is legal as well

void ProcessMammal(Mammal someMammal);

Action<Mammal> processMethod = ProcessMammal;
Action<Animal> someAction = processMethod;

Of course this is illegal because someone can pass any Animal to someAction, where as the ProcessMammal expects anything thats Mammal or more specific ( lesser than Mammal ). Which is why someAction has to only be Action or anything more specific (Action)

However this is introducing a layer of delegates in the middle, is it necessary that for a contravariant projection to happen there has to be a delegate in the middle? And if we were to define Process as an interface we would declare the argument parameter as a contravariant type only because we wouldn't want someone to be able to do what I had shown above with delegates?

public interface IProcess<out T>
{
    void Process(T val);
}

Best Answer

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.

Related Solutions

C# – LINQ Aggregate algorithm explained

The easiest-to-understand definition of Aggregate is that it performs an operation on each element of the list taking into account the operations that have gone before. That is to say it performs the action on the first and second element and carries the result forward. Then it operates on the previous result and the third element and carries forward. etc.

Example 1. Summing numbers

var nums = new[]{1,2,3,4};
var sum = nums.Aggregate( (a,b) => a + b);
Console.WriteLine(sum); // output: 10 (1+2+3+4)

This adds 1 and 2 to make 3. Then adds 3 (result of previous) and 3 (next element in sequence) to make 6. Then adds 6 and 4 to make 10.

Example 2. create a csv from an array of strings

var chars = new []{"a","b","c", "d"};
var csv = chars.Aggregate( (a,b) => a + ',' + b);
Console.WriteLine(csv); // Output a,b,c,d

This works in much the same way. Concatenate a a comma and b to make a,b. Then concatenates a,b with a comma and c to make a,b,c. and so on.

Example 3. Multiplying numbers using a seed

For completeness, there is an overload of Aggregate which takes a seed value.

var multipliers = new []{10,20,30,40};
var multiplied = multipliers.Aggregate(5, (a,b) => a * b);
Console.WriteLine(multiplied); //Output 1200000 ((((5*10)*20)*30)*40)

Much like the above examples, this starts with a value of 5 and multiplies it by the first element of the sequence 10 giving a result of 50. This result is carried forward and multiplied by the next number in the sequence 20 to give a result of 1000. This continues through the remaining 2 element of the sequence.

Live examples: http://rextester.com/ZXZ64749
Docs: http://msdn.microsoft.com/en-us/library/bb548651.aspx

Addendum

Example 2, above, uses string concatenation to create a list of values separated by a comma. This is a simplistic way to explain the use of Aggregate which was the intention of this answer. However, if using this technique to actually create a large amount of comma separated data, it would be more appropriate to use a StringBuilder, and this is entirely compatible with Aggregate using the seeded overload to initiate the StringBuilder.

var chars = new []{"a","b","c", "d"};
var csv = chars.Aggregate(new StringBuilder(), (a,b) => {
    if(a.Length>0)
        a.Append(",");
    a.Append(b);
    return a;
});
Console.WriteLine(csv);

Updated example: http://rextester.com/YZCVXV6464

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

Best Answer

Related Solutions

C# – LINQ Aggregate algorithm explained

Java – Covariance, Invariance and Contravariance explained in plain English

Related Topic