Invariants, Covariants and Contravariants

For one of the projects that I worked on, I needed to learn Scala and I encountered one particular problem while I was writing a trait (Scala's word for Java 'interface'):

trait DList[+T] {
  def isEmpty: Boolean  def value: T  def next: DList[T]
  def add(elem: T): DList[T]
}

Simple generic immutable dynamic linked list. However, 'add' method is the one that was causing a trouble during the compilation and message is somewhat incomprehensible: 'covariant type T occurs in contravariant position in type T of value elem'. What the hell is this and is there a workaround? I decided to do additional research and to solve this.

What I know so far:

I can't say that I never heard for terms, covariants and contravariants. It has something to do with the generic types and type parameter (those types in <> brackets) inheritance during the variable declaration. Very important: not during the class definition and not during the class instantiation. They appear (briefly) in Oracle's Java certification for Programmer II, so I will first explain what I know so far in Java:
Let's assume that we have a following relationship. For example: class Cat is a subtype of the Animal class

Relationship of animals

When you declare generic variable like this:

List<? extends Animal> covariantAnimalList;

this is called covariant, and when you declare generic variable like this:

List<? super Animal> contravariantAnimalList;

this is called contravariant.

All what I knew is that covariantAnimalList cannot add any Animal objects (or its subtypes), but it can return Animal objects. In fact, it will not accept any argument that is a generic type parameter.
For contravariantAnimalList I know that you can add any Animal object (or its supertypes), but you cannot return any Animal object from it. It will not return any value that is a generic type parameter.

They are commonly used in producer/consumer pattern, where you use covariant generic type to read (and maybe remove) data from the list or queue, while you use contravariant generic type for inserting data to the list or queue.

Now let's demystify what these variants really are. Examples are in Scala, but same definitions apply in Java too.

Invariance

These variants define the inheritance relationship between type parameters. By default, type parameters in generic type do not have any relationship between themselves. So if Cat is a subtype of Animal and if it is a type parameter then there are no relationship between generic classes that uses them.
For example, if you have trait defined like this:

trait DList[T]

and declared values like this:

val animalList : DList[Animal]
val catList : DList[Cat]

There is no way that compiler will allow you to do something like this:

animalList = catList // compiler error

Cat and Animal may be related, but in scope of type parameter there are no relationship.
This is called invariance.

Of course, if you have:

val animalList : DList[Animal]
val animalLinkedList : LinkedList[Animal]

where LinkedList extends DList, then this is compiled without problems:

animalList = animalLinkedList

Remember, variance only defines relationship of generic type parameters, not generic classes itself.

Invariance Example

Covariance:

Covariant type is probably the one that you though that should be default:

Covariance Example

In scala, it is defined like this:

trait DList[+T]

Here, type parameters retain their relationship and previous example will work without problems:

val animalList : DList[Animal]
val catList : DList[Cat]
animalList = catList

Of course, this will not work:

val albinoCatList : DList[AlbinoCat]
val catList : DList[Cat]
albinoCatList = catList // compiler error

Contravariance:

As name suggests, here, the type parameters relationships are reversed:

Contravariance Example

In scala, it is defined like this:

trait DList[-T]

As you suspected, this code will no longer compile:

val animalList : DList[Animal]
val catList : DList[Cat]
animalList = catList // compiler error

However, by everyone's surprise, these lines of code WILL compile:

val albinoCatList : DList[AlbinoCat]
val catList : DList[Cat]
albinoCatList = catList

Remember, in contravariance (look for the clue in the name) relationship between type parameters is reversed.

Covariant type T occurs in contravariant position in type T of value elem

Now, let's back to the problem from the beginning of the text and let me explain what could happen if compiler allowed such "hack".
Assume that we have developed such generic type:

trait Cage[+T] {
  def getVar: T  def setVar[T](elem: T): Unit
}

// this class will not compile, but let's assume that it can
class SteelCage[+T] extends Cage[T] {
  var captive: T
  override def getVar: T = captive
  override def setVar[T](elem: T): Unit = captive = elem
}

Class SteelCage expands from trait Cage and it is just a data holder with getters and setters. Of course, in Scala, you will almost never define mutable variables and you will need to modify your class logic to be immutable, but for the sake of the test we will let captive slip as var.

We will use our covariance figure:

Covariance with cages

Examine the following code:

val catCage : Cage[Cat] = new SteelCage[Cat]();  // 1
catCage.setVar(new Cat()) // 2
val animalCage : Cage[Animal] = catCage; // 3
animalCage.setVar(new Dog()) // 4

Let's walk through this code:
One line 1, we declared a value of type Cage[Cat] and assigned it an instance of SteelCage[Cat].
We then, in next line 2, set the variable to the Cat instance. So far everything is looking good.
Now, on line 3, we declare new value of type Cage[Animal] and reference value catCage, which is an instance of SteelCage[Cat] at runtime. Since that we are using covariance, this command is valid as Cage[Cat] is a subtype of Cage[Animal]
Now take a look at line 4. We are setting animalCage var to the instance of the Dog!! animalCage is defined as Cage[Animal] so Dog is acceptable, but at the runtime animalCage is actually an instance of SteelCage[Cat]!! This is an error, as we just slipped Dog into the Steel Cage that can accept only cats!!

This is the reason why this message exists 'covariant type T occurs in contravariant position in type T of value elem' (although you might get different compile error for different situation, but eventually you will get this one at the end). That is why, in covariance, you are not allowed to take an argument of type parameter, because, with the proper casting, you can end up at assigned variable that is not in the proper relationship.

Contravariant type T occurs in covariant position in type T of value elem

Let's see the contravariant example:
Here is our class in contravariant example (and yes most things will not compile):

// this class will not compile, but let's assume that it can
trait Cage[-T] {
  def getVar: T  def setVar[T](elem: T): Unit
}

// this class will not compile, but let's assume that it can
class SteelCage[-T] extends Cage[T] {
  var captive: T
  override def getVar: T = captive
  override def setVar[T](elem: T): Unit = captive = elem
}

Here is our contravariance figure:

Contravaraince with Cages

Let's look at a slightly different code:

val catCage : Cage[Cat] = new SteelCage[Cat]();  // 1
catCage.setVar(new Cat()) // 2
val albinoCatCage : Cage[AlbinoCat] = catCage; // 3
val albinoCat : AlbinoCat = albinoCatCage.getVar() // 4

First two lines are the similar from the previous example. Now, on line number 3 it gets more interesting. We are declaring albinoCatCage that references SteelCat[Cat]. By the rules of contravaraince this is perfectly fine as Cage[Cat] is a subtype of Cage[AlbinoCat]. Keep in mind that relationship between types Cat and AlbinoCat is reversed.
Line 4 is where the all hell broke lose. albinoCatCage will return an instance of Cat because albinoCatCage references an instance of SteelCage[Cat] which holds a Cat. However, value at the left side accepts only AlbinoCat type and its subtypes, and there is no way that it could have known that on runtime albinoCatCage will return a Cat instance which is a super type of AlbinoCat! You can, of course, change the type of albinoCat value to Cat, but Cage[AlbinoCat] clearly states that it can return AlbinoCat and all its subtypes, not its super types.
This is the reason why error 'Contravariant type T occurs in covariant position in type T of value elem' to prevent such possibilities.

Solution to the problem at the beginning:

Well, you should change the architecture of these classes. Generally, in Scala, you will mostly use immutable data, so there will not be many situations where you will face such problem.
To return to the my example from the beginning regarding the DList. To explain: Add method should be adding new element to the list, by creating whole new List and adding it at the beginning. Remember: Scala favors immutable data types. However, Scala compiler don't know what I am going to do with the argument (I might somehow, try to assign it in the existing DList implementation), so I have to using bounding types to make compiler happy.

trait DList[+T] {
  def isEmpty: Boolean  
  def add[S >: T](elem: S): DList[S]
}

This updated 'add' method accepts the argument that is a subtype of T or has an exact type of T. This keeps compiler happy, as it knows that I cannot reassign some internal variable due to the type mismatch.
Compiler will not allow me to have var in covariant or contravariant anyway, but that is another story.

Conclusion:

I hope that this example will give you a much clearer picture on what are invariants, covariants and contravariants and reason why they have limited functionalities in some cases. Always, remember that generic type parameters do not inherit relationships with their 'normal' type counterparts and consider that, by default, there are no relationships between them. If you decide to give them one of two possible relationship models (covariance or contravariance), then be aware of the limitations of each approach. Sometimes, those limitations are just the ones that you need, especially in producer/consumer pattern where you want to make sure that producer can only add things and never be able to get anything; while the consumer can only take things, but never put anything back in it.