Can anyone explain the concept of covariance and contravariance in programming language theory?
Covariance is simple. Consider an immutable collection class like List, which is parameterized by a type parameter T, so that List[T] contains elements of type T.
Then, List[T] is covariant in T if the following is true:
S is a subtype of T if and only if List[S] is a subtype of List[T]
For example, if Apple is a Fruit, then 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 read_from_list(l: List[Fruit]) {
for (x in l) {
print(x.ripeness)
}
}
read_from_list(apples) // apples: List[Apple]
However, this is impossible:
def write_to_list(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 shown above. Hence we should only like immutable collection classes to be covariant!