Object hierarchies

The common use of the terms contravariance and covariance in programming has come to mean something a little more specific than in physics and math - but still often related to the inputs and outputs of functions so lets look at this common usage first.

The whole idea relates to the hierarchy of types.

If type B is derived from type A that is it "inherits" from A or, put another way,  A is the base class for B - then it contains every method and property that type A does and more.

In this sense type B is "bigger" than type A.

You can see that the type system provides a way of ordering classes.  (Notice that not all classes are on the same branch of the type hierarchy and so not all classes can be compared in this way i.e. we only have a partial ordering.)

The idea that B is in some way "bigger" than A is an important idea. Unfortunately it has long been the case that we use the less than symbol to show that a type is derived from another type which is perhaps the wrong way round.

That is if we write A>B  then A is "higher" in the type hierarchy than B or in other words B is derived from A.

The substitution principle

If B derives from A then A>B and B inherits or contains everything that A has to offer.

As B contains everything that A does you can use a B anywhere that you could have used an A. Of course you can't always use an A in place of a B so the relationship is asymmetrical.

This is formally known as the Liskov Substitution principle.

In fact the full "principle" is a little wider than this as it holds that anything that is true of an A should be true of a B and in general this is difficult to achieve - but you get the general idea.

In practice it is a more a guiding principle than something that is enforced all of the time. 

Inferred type relationships

Looking at the substitution principle the other way round we can use it to define the hierarchical type relationship between types.

That is if type B can be used anywhere a type A would be ok then you can say that type A is a base type for type B and B<A.

This is a reasonable idea because if B can always be used in place of A then it has everything that A has and perhaps more.

This is a useful idea when you are working with types that are not explicitly defined within a type hierarchy by being explicitly derived from one another - as is the case for delegates say, see later.

Functions

Now let's look at these ideas when applied to functions.

If you define a function which accepts an object of type A as its input parameter and returns a derived object of type B as its output

i.e. f(A)->B and A>B.

Then, by the substitution principle or just because a derived class B has all of the properties of A, you can use a B as the input and treat the return a B as the result. In other words f(B) is legal. 

That is if you have a function:

B MyFunction(A param){
 return new B
}

you can write

A MyA=MyFunction(new B);

That is if A>B the input parameter A can be a B because it has everything an A does. But by the usual rules the B that the function returns as its result can be treated as an A because a B has everything an A has. So on input an A can be replaced by a subclass and on output a B can be replaced by a superclass. 

So it seems that input parameters are contravariant and output parameters i.e. results are covariant.

To see that this is so we have to shift our viewpoint a little.

Let's think about this from the point of view of the function for a moment. Consider two functions that just differ in the type of their input parameters with A>B:

void MyFunction1(A param){
}
void MyFunction2(B param){
}

By the substitution principle MyFunction1 can accept a B as its input and so can be used anywhere you use a MyFunction2.

Hence by the reverse substitution principle you have to regard  MyFunction1 as derived from MyFunction2 and

MyFunction1<MyFunction2

That is changing the input parameter type from A to B where A>B results in MyFunction1<MyFunction2

You can now see clearly why this is contravariance. Changing the parameter from type A to type B in the function definition where A>B results in MyFunction1<MyFunction2 - the resulting type ordering goes the other way.

Now lets repeat the argument but with two functions that only differ by their output type where A>B:

A MyFunction1(){
 return new A;
}
B MyFunction2(){
 return new B;
}

In this case the by the substitution principle it is clear that MyFunction2 can be used anywhere MyFunction1 can, because it returns a B which can always be treated as an A, and hence MyFunction2 has to be considered as derived from MyFunction1 i.e.

MyFunction1>MyFunction2.

Thus A>B results in MyFunction1>MyFunction2.

You can see that changing the output type from A to B i.e. going towards more derived makes the new function more derived and the change is covariant.

So changing input parameter type to be more derived makes the function less derived i.e. contravariant change and changing the output type to be more derived makes the function more derived i.e. covariant change.

The general principle

Now that you have looked at the way that a change to a function effects its type we can generalise the idea of covariance and contravariance to any situation - not just where functions are involved.

Suppose we have two types A and B and we have a modification, or transformation T,  that we can make to both of them to give new types T(A) and T(B).

• If T is a covariant transformation we have A>B implies T(A)>T(B).
• If T is a contravariant transformation then we have A>B implies T(A)<T(B).
• It is also possible that neither relationship applies that is A>B doesn't imply anything about the relationship between T(A) and T(B). In this case T is referred to as invariant - which isn't really a good name.

Our earlier function example can be recast into this form by inventing  the transformation T that converts a type into a function with a parameter of that type. As already worked out T is clearly contravariant.

That is, T(A)=function(A) and T(B) = function(B), where function(A) is any function returning any type and accepting a parameter of type A and, as we have demonstrated in the previous section, A>B implies:

T(A)=function(A)<function(B)=T(B)

In the same way a transformation that converts a type into a function that returns the type is covariant.

That is, T(A)=A function() and T(B)=B function, where   A function is any function of any parameter type that returns a type A, and B function is any function of any parameter types that returns a type B, then A>B implies:

T(A)=A function()>B function=T(B)

This is a completely general idea.

For example consider the transformation that converts a type into an array of that type i.e. T(A) is and array of type A or A[]. If A>B an array of B  can be substituted for an array of A and so A[]>B[]. Hence forming an array is covariant. 

<ASIN:1871962439>

<ASIN:1871962587>