Invariance, Covariance and Contravariance

While learning Scala I spent a fair amount of time getting my head around covariant and contravariant concepts. Just recently I found myself tryying to explain these to a collegue. I've since refined my explanation and decided to write it down for all those people who want a clear, maths free explanation.

Invariance

Let's consider a simple domain model. We have a base class 'Employee' and a sub-class 'Manager':

scala> class Employee(val number: String, val name: String)
defined class Employee

scala< class Manager(number: String, name: String, val department: String) extends Employee(number, name)
defined class Manager

Next, we have an award class that we implement using a parameterised recipient type so that awards can be used for more than just our Employee/Manager model:

scala> class Award[T](val recipient: T)
defined class Award

So, lets create an award that is for one of our managers:

scala> val mike = new Manager("1", "Mike", "Sales")
mike: Manager = Manager@712c20d9

scala> val managerAward = new Award[Manager](mike)
managerAward: Award[Manager] = Award@411a9435

All well and good. We have a manager award instance. However, say we have a variable that is of type Award[Employee]. It would seem natural to be able to assign our manager award to this variable as a manager is a type of employee, so their award should also be part of the general set of awards given to employees, right? Well...

scala> val employeeAward: Award[Employee] = managerAward
<console>:12: error: type mismatch;
 found   : Award[Manager]
 required: Award[Employee]
Note: Manager <: Employee, but class Award is invariant in type T.
You may wish to define T as +T instead. (SLS 4.5)
       val employeeAward: Award[Employee] = managerAward

So, we see that this is not possible. We also can't add our manager award to a list of awards given to employees, even though it seems natural that we should be able to do so:

scala> val awards = List[Award[Employee]](managerAward)
<console>:12: error: type mismatch;
 found   : Award[Manager]
 required: Award[Employee]
Note: Manager <: Employee, but class Award is invariant in type T.
You may wish to define T as +T instead. (SLS 4.5)
       val awards = List[Award[Employee]](managerAward)

This is an example of an invariant type. Even though the parameterised type is a subclass of the more general one, we can't assign it to an instance that has been parameterised with the more general type. This is the standard generics model of Scala and is also the way that the Java language handles generics.

Covariance

Fortunately, Scala's type system allows us to overcome this problem by allowing covariant types. We can redefine the awards class using a plus (+) character on the type to indicate that it is covariant:

scala> class Award[+T](val recipient: T)
defined class Award

Now, we can create a new manager award and can assign it to a variable of type employee award or add it to a collection of employee awards:

scala> val managerAward = new Award[Manager](mike)
managerAward: Award[Manager] = Award@7796649

scala> val employeeAward: Award[Employee] = managerAward
employeeAward: Award[Employee] = Award@7796649

scala> val awards = List[Award[Employee]](managerAward)
awards: List[Award[Employee]] = List(Award@7796649)

By using covariant types we are in effect saying that for any parameterised class its super classes include those parameterised with any of the superclasses of the type used as the parameter. Java provides a very basic mechanism for supporting covariance with the extends keyword in generic declarations:

Award<? extends Employee> employeeAward = managerAward;

However, the Java solution is less powerful because it is the variable using the instance that defines whether it allows covariance rather than allowing this to be encapsulated inside the class itself.

Contravariance

It is slightly more difficult to explain contravariance, and we first need to expand our domain model slightly. We now want to create different classes of awards and restrict who they can be presented to. Firstly we start by adding an additional generic parameter to the Award class to control the class of the award. We also create a couple of example awards restricted on this parameter:

class Award[+T, V](val recipient: T)

class AttendanceAward[T](recipient: T) extends Award[T, Employee](recipient)
class TeamLeadershipAward[T](recipient: T) extends Award[T, Manager](recipient)

The above effectively states that Attendance Awards are available to employees, while a Team Leadership Award can only be presented to Managers. Let's add a couple of functions that deal with presenting the awards:

def presentManagementAward(award: Award[Manager, Manager]) = { /* lots of pomp */ }
def presentEmployeeAward(award: Award[Employee, Employee]) = { /* a simple affair */ }

These state that a management award (with all the pomp) must be an award for managers that is presented to a manager, while an simple affair is available to an employee receiving and employee award. Wait, what happens when we want to present an employee class award to a manager with all the pomp?

scala> presentManagementAward(new AttendanceAward(mike))
<console>:14: error: type mismatch;
 found   : AttendanceAward[Manager]
 required: Award[Manager,Manager]
Note: Employee >: Manager (and AttendanceAward[Manager] <: Award[Manager,Employee]), but class Award is invariant in type V.
You may wish to define V as -V instead. (SLS 4.5)
       presentManagementAward(new AttendanceAward(mike))

We can't do this as the presentManagementAward function is expecting an award of class manager given to a manager but instead we are passing an award of class employee. However, in this case it seems wrong that this doesn't work. Why shouldn't the manager also be able to receive more general awards? It turns out that we can achieve this my modifying the award classifier to be contravariant. This makes it possible to substitute a more general parameter. If we can present a management class award then we can also present a more general employee award:

class Award[+T, -V](val recipient: T)

scala> presentManagementAward(new AttendanceAward(mike))

So there we have it, invariance, covariance and contravariance.