Difference between Covariance and Contra-variance in programming languages

Question

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

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!