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

Question

Can anyone explain the concept of covariance and contravariance in programming language theory?

Prohibitive

http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science) – Outrank

I smell a homework question. – Traverse

possible duplicate of C# : Is Variance (Covariance / Contravariance) another word for Polymorphism? – Butch

Answer 1

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!

Untoward

Good definition, but it misses the fact that not only types can be treated as co/contravariant. For example, Java List<T> isn't either, but Java wildcards let you treat in either covariant or contravariant fashion at point of use (rather than declaration) - of course, restricting the set of operations on the type to those that are actually covariant and contravariant for it. – Puerperium

I believe that List<? extends Fruit> is a kind of existential type: i.e. List[T] forSome T <: Fruit - the forSome T <: Fruit is itself a type in this instance. Java is still not covariant in this type though. For example a method accepting a List<? extends Fruit> would not accept List<? extends Fruit> – Untoward

OTOH, S <= T iff List[T] <= List[S] with respect to the add operation, since we can add things of type S to a List[T] if S <= T. So lists are contravariant with respect to the add operation. – Austronesian

I would have found it very useful if you had expanded your answer to demonstrate contravariance using fruit. I feel like after reading it I understand covariance but still don't understand contravariance. – Babushka

Answer 2

There is a distinction being made between covariance and contravariance.
Very roughly, an operation is covariant if it preserves the ordering of types, and contravariant if it reverses this order.

The ordering itself is meant to represent more general types as larger than more specific types.
Here's one example of a situation where C# supports covariance. First, this is an array of objects:

var objects = new object[3];
objects[0] = new object();
objects[1] = "Just a string";
objects[2] = 10;

Of course it is possible to insert different values into the array because in the end they all derive from System.Object in .Net framework. In other words, System.Object is a very general or large type. Now here's a spot where covariance is supported:
assigning a value of a smaller type to a variable of a larger type

var strings = new string[] { "one", "two", "three" };
objects = strings;

The variable objects, which is of type object[], can store a value that is in fact of type string[].

Think about it — to a point, it's what you expect, but then again it isn't. After all, while string derives from object, string[] DOES NOT derive from object[]. The language support for covariance in this example makes the assignment possible anyway, which is something you'll find in many cases. Variance is a feature that makes the language work more intuitively.

The considerations around these topics are extremely complicated. For instance, based on the preceding code, here are two scenarios that will result in errors.

// Runtime exception here - the array is still of type string[],
// ints can't be inserted
objects[2]=10;

// Compiler error here - covariance support in this scenario only
// covers reference types, and int is a value type
var ints = new int[] { 1, 2, 3 };
objects = ints;

An example for the workings of contravariance is a bit more complicated. Imagine these two classes:

public partial class Person: IPerson 
{
    public Person() 
    {
    }
}

public partial class Woman: Person
{
    public Woman()
    {
    }
}

Woman is derived from Person, obviously. Now consider you have these two functions:

static void WorkWithPerson(Person person)
{
}

static void WorkWithWoman(Woman woman)
{
}

One of the functions does something(it doesn't matter what) with a Woman, the other is more general and can work with any type derived from Person. On the Woman side of things, you now also have these:

delegate void AcceptWomanDelegate(Woman person);

static void DoWork(Woman woman, AcceptWomanDelegate acceptWoman)
{
    acceptWoman(woman);
}

DoWork is a function that can take a Woman and a reference to a function that also takes a Woman, and then it passes the instance of Woman to the delegate. Consider the polymorphism of the elements you have here. Person is larger than Woman, and WorkWithPerson is larger than WorkWithWoman. WorkWithPerson is also considered larger than AcceptWomanDelegate for the purpose of variance.

Finally, you have these three lines of code:

var woman = new Woman();
DoWork(woman, WorkWithWoman);
DoWork(woman, WorkWithPerson);

A Woman instance is created. Then DoWork is called, passing in the Woman instance as well as a reference to the WorkWithWoman method. The latter is obviously compatible with the delegate type AcceptWomanDelegate — one parameter of type Woman, no return type. The third line is a bit odd, though. The method WorkWithPerson takes a Person as parameter, not a Woman, as required by AcceptWomanDelegate. Nevertheless, WorkWithPerson is compatible with the delegate type. Contravariance makes it possible, so in the case of delegates the larger type WorkWithPerson can be stored in a variable of the smaller type AcceptWomanDelegate. Once more it's the intuitive thing: if WorkWithPerson can work with any Person, passing in a Woman can't be wrong, right?

By now, you may be wondering how all this relates to generics. The answer is that variance can be applied to generics as well. The preceding example used object and string arrays. Here the code uses generic lists instead of the arrays:

var objectList = new List<object>();
var stringList = new List<string>();
objectList = stringList;

If you try this out, you will find that this is not a supported scenario in C#. In C# version 4.0 as well as .Net framework 4.0, variance support in generics has been cleaned up, and it is now possible to use the new keywords in and out with generic type parameters. They can define and restrict the direction of data flow for a particular type parameter, allowing variance to work. But in the case of List<T>, the data of type T flows in both directions — there are methods on the type List<T> that return T values, and others that receive such values.

The point of these directional restrictions is to allow variance where it makes sense, but to prevent problems like the runtime error mentioned in one of the previous array examples. When type parameters are correctly decorated with in or out, the compiler can check, and allow or disallow, its variance at compile time. Microsoft has gone to the effort of adding these keywords to many standard interfaces in .Net framework, like IEnumerable<T>:

public interface IEnumerable<out T>: IEnumerable
{
    // ...
}

For this interface, the data flow of type T objects is clear: they can only ever be retrieved from methods supported by this interface, not passed into them. As a result, it is possible to construct an example similar to the List<T> attempt described previously, but using IEnumerable<T> :

IEnumerable<object> objectSequence = new List<object>();
IEnumerable<string> stringSequence = new List<string>();
objectSequence = stringSequence;

This code is acceptable to the C# compiler since version 4.0 because IEnumerable<T> is covariant due to the out specifier on the type parameter T.

When working with generic types, it is important to be aware of variance and the way the compiler is applying various kinds of trickery in order to make your code work the way you expect it to.

There's more to know about variance than is covered in this chapter, but this shall suffice to make all further code understandable.

Ref:

• PROFESSIONAL Functional Programming in C#

Misdo

Answer 3

Variance, Covariance, Contravariance, Invariance

Type(T)

composite data type - is a type which is built out of another type. For example it can be generic, container(collection), optional^[example]

method's type - method's parameter type(pre-condition) and return type(post-condition)^[About]

Variance

Variance - is about assignment compatibility. It is an ability to use a derived type instead of original type. It is not parent-child relationship

X(T) - `composite data type` or `method type` X, with type T

Covariance(same subtyping direction) you are able to assign more derived type than original type(strives for -> X(C))

X(T) covariant or X(T1) is covariant to X(T2) when relation T1 to T2 is the same as X(T1) to X(T2)

Contravariance(opposite subtyping direction) you are able to assign less derived type then original type(strives for -> X(A))

X(T) contravariant or X(T1) is contravariant to X(T2) when relation T1 to T2 is the same as X(T2) to X(T1)

Invariance neither Covariance not Contravariance. There is exists also ^{[Class Invariant]}

Examples

Class directions, pseudocode

//C -> B -> A

class A {}
class B: A {}
class C: B {}

Reference type Array in Java is covariant

A[] aArray = new A[2];
B[] bArray = new B[2];

//A - original type, B - more derived type
//B[] is covariant to A[]
aArray = bArray;

class Generic<T> { }

//A - original type, B - more derived type
//Generic<B> is covariant to Generic<A>
//assign more derived type(B) than original type(A)
Generic<? extends A> ref = new Generic<B>(); //covariant

//B - original type, A - less derived type
//Generic<B> is contravariant to Generic<A>
//assign less derived type(A) then original type(B)
Generic<? super B> ref = new Generic<A>(); //contravariant

<sub_type> covariant/contravariant to <super_type>

Swift

• Array
• Generic
• Closure

Swift Array is covariance

let array:[B] = [C()]

Swift Generic is Invariance

class Wrapper<T> {
    let value: T
    
    init(value: T) {
        self.value = value
    }
}

let generic1: Wrapper<A> = Wrapper<B>(value: B()) //ERROR: Cannot assign value of type 'Wrapper<B>' to type 'Wrapper<A>'
let generic2: Wrapper<B> = Wrapper<A>(value: A()) //ERROR: Cannot assign value of type 'Wrapper<A>' to type 'Wrapper<B>'

Swift closure

closure’s return type is covariance closure’s argument type is contravariance

var foo1: (A) -> C = { _ in return C() }
let foo2: (B) -> B = foo1

covariance
() -> B = () -> C

contravariance 
(A) -> Void = (B) -> Void

[Liskov principle]

[Java generics]

Poynter

Answer 4

Both C# and the CLR allow for covariance and contra-variance of reference types when binding a method to a delegate. Covariance means that a method can return a type that is derived from the delegate’s return type. Contra-variance means that a method can take a parameter that is a base of the delegate’s parameter type. For example, given a delegate defined like this:

delegate Object MyCallback(FileStream s);

It is possible to construct an instance of this delegate type bound to a method that is prototyped

Like this:

String SomeMethod(Stream s);

Here, SomeMethod’s return type (String) is a type that is derived from the delegate’s return type (Object); this covariance is allowed. SomeMethod’s parameter type (Stream) is a type that is a base class of the delegate’s parameter type (FileStream); this contra-variance is allowed.

Note that covariance and contra-variance are supported only for reference types, not for value types or for void. So, for example, I cannot bind the following method to the MyCallback delegate:

Int32 SomeOtherMethod(Stream s);

Even though SomeOtherMethod’s return type (Int32) is derived from MyCallback’s return type (Object), this form of covariance is not allowed because Int32 is a value type.

Obviously, the reason why value types and void cannot be used for covariance and contra-variance is because the memory structure for these things varies, whereas the memory structure for reference types is always a pointer. Fortunately, the C# compiler will produce an error if you attempt to do something that is not supported.

Caravel