# Covariance and contravariance in Scala

This post explains concepts of covariance and contravariance. It focuses on real world metaphors and on code examples that show how those concepts can be used in Scala. Metaphors are borrowed from Erik Meijer's talk Contravariance is the Dual of Covariance Implies Iterable is the Dual of Observable (Making Money Using Math) [Meijer2014].

## Covariance

First example of the covariance section uses model of drinks presented below.

Imagine that your employer promised a new soft drink vending machine. Covariance means that in its place he can install a cola or tonic water vending machine because both cola and tonic water are subtypes of soft drink. Let's turn this description into Scala code.

The method `install` accepts a `VendingMachine` of type `SoftDrink` or subtypes of `SoftDrink` (`Cola` and `TonicWater`). This is possible because type parameter `A` is prefixed with a +. It indicates that subtyping is covariant in that parameter. Alternatively, it can be said that class `VendingMachine` is covariant in its type parameter `A`. Next code snippet shows covariant subtyping because `Cola` and `TonicWater` are subtypes of `SoftDrink`.

However, a `VendingMachine` of type `Drink` can't be passed to the method `install` because `Drink` is a supertype of `SoftDrink`. That would be contravariant subtyping. Contravariance is explained later.

To sum up.

If `A` is a subtype of `B` then `VendingMachine[A]` should be a subtype of `VendingMachine[B]`. This property is called covariant subtyping [Odersky2014].

### Use restrictions of covariant type parameter

When a type parameter is declared as covariant, the number of positions where it can be safely used is reduced. Thankfully, Scala compiler prevents from the use of covariant type parameter in positions that could lead to potential errors. Next example, this time from Java, shows why this is important.

Unfortunately, arrays in Java are covariant. This allows code below to compile because `String` is a subtype of `Object`. Therefore, covariant subtyping can be applied.

If `objects` would be modified with value of type other than `String` then `ArrayStoreException` would be thrown.

Scala fixes this problem by making its Array type invariant in its type parameter.

Scala's `Array` type parameter doesn't have covariance annotation (+ prefix). If it had then the method `def update(i: Int, x: T): Unit` could lead to potential runtime errors and in Scala it wouldn't even compile.

In general, covariant type parameter can be used as immutable field type, method return type and also as method argument type if the method argument type has a lower bound. Because of those restrictions, covariance is most commonly used in producers (types that return something) and immutable types. Those rules are applied in the following implementation of vending machine.

The method `def addAll[B >: A](newItems: List[B]): VendingMachine[B]` has very useful characteristic, that is, a lower bound makes the method `addAll` very flexible as seen below.

`SoftDrink` is the common supertype of both `TonicWater` and `Cola`, so the method `addAll` above returns instance of `VendingMachine` of type `SoftDrink`.

#### Covariant (and contravariant) type parameter as mutable field type

Type parameter with variance annotation (covariant + or contravariant -) can be used as mutable field type only if the field has object private scope (`private[this]`). This is explained in Programming In Scala [Odersky2008].

Object private members can be accessed only from within the object in which they are defined. It turns out that accesses to variables from the same object in which they are defined do not cause problems with variance. The intuitive explanation is that, in order to construct a case where variance would lead to type errors, you need to have a reference to a containing object that has a statically weaker type than the type the object was defined with. For accesses to object private values, however, this is impossible.

Next example shows how rule above could be applied in practice. Imagine that you are creating a sci-fi shooter game where player can shoot with different kinds of bullets.

Bullets are contained in the the ammo magazine as seen in the next code listing. Notice that class `AmmoMagazine` is covariant in its type parameter `A`. It also contains mutable field `bullets` which compiles because of object private scope. Everytime the method `giveNextBullet` is invoked, bullet from the `bullets` list is removed. `AmmoMagazine` can't be refilled with bullets and there is no way of introducing this feature into this class because that would have led to potential runtime errors.

Class `AmmoMagazine` is used in the `Gun` class. `Gun` has method `reload` which thanks to the covariant subtyping can be reloaded with both `AmmoMagazine[NormalBullet]` and `AmmoMagazine[ExplosiveBullet]`, and in general with `AmmoMagazine` of any subtype of `Bullet`.

## Contravariance

This section is very similar to the previous one because contravariance is simply the opposite of covariance. Example of contravariance section uses model of items presented below.

Long time ago all kinds of trash could be put into single garbage can. Nowadays, trash must be segregated into different garbage cans - one for plastic items, one for paper items and so on. Contravariance means that if you need a garbage can for plastic items, you can simply set in its place a garbage can for items, because item is the supertype of plastic item. In Scala, this can be expressed as follows.

The method `setGarbageCanForPlastic` accepts a `GarbageCan` of type `PlasticItem` or supertype of `PlasticItem` (`Item`). This is possible because type parameter `A` is prefixed with a -. It indicates that subtyping is contravariant in that parameter. Alternatively, it can be said that class `GarbageCan` is contravariant in its type parameter `A`. Next code snippet shows contravariant subtyping because `Item` is the supertype of `PlasticItem`.

However, a `GarbageCan` of type `PlasticBottle` can't be passed to the method `setGarbageCanForPlastic`, because `PlasticBottle` is the subtype of `PlasticItem`. That would be covariant subtyping.

To sum up.

If `A` is a subtype of `B` then `GarbageCan[B]` should be a subtype of `GarbageCan[A]`. This property is called contravariant subtyping.

### Use cases for contravariant type parameter

Contravariant type parameter is usually used as method argument type, therefore, contravariance is most commonly associated with consumers (types that accept something). It can also be used as mutable field type if the field has object private scope as explained before. Scala compiler prevents from the use of contravariant type parameter in positions that could lead to potential errors. If contravariant type parameter would have been used in illegal position such as method return type then Scala compiler would have reported an error. Example use of contravariant type parameter is applied in the following implementation of garbage can.

## Real world examples of covariance and contravariance

Covariance and contravariance is very common in functional style programming. Many libraries used by developers on a daily basis use variance annotations to make library types more flexible by allowing the use of covariant and contravariant subtyping.

### Function type (T) => R

One of the most common type used in the functional programming style is function (T) => R.

In this type both contravariance and covariance is used. `T` is contravariant type parameter because it is used as `apply` argument type and `R` is covariant type parameter because it is used as `apply` return type. This makes type `Function1` very flexible. Let's examine how contravariance in `Function1` helps its users achieve more with less code. Below code snippet presents music instruments model.

Next code snippet shows a function that returns true if `MusicInstrument` is vintage.

Method `isVintage` can be used to filter both `List[Piano]` and `List[Guitar]`. This is possible because contravariant subtyping can be applied. If `T` from function `(T) => R` was not a contravariant type parameter then two versions of `isVintage` function would have to be implemented, one for `Piano` and one for `Guitar`. See it in action in the code listing below.

Example above only took advantage of contravariant subtyping but covariant subtyping can be just as useful.

### Immutable container types - Option, Collections

Scala immutable container types such as `Option` and `List` are covariant in their type parameter. If this wasn't the case then in the code snippet below, separate `getPrices` method for each subtype of `MusicInstrument` would have to be implemented. However, with the use of covariant subtyping, one method is enough.

### RxScala

Asynchronous and event-based programs have gained a lot of popularity in the recent years. It used to be really challenging to write such programs but with the arrival of the Reactive Extensions things became much easier. Quote below explains what are Reactive Extensions in short [Reactivex.io].

ReactiveX is a library for composing asynchronous and event-based programs by using observable sequences.

It extends the observer pattern to support sequences of data and/or events and adds operators that allow you to compose sequences together declaratively while abstracting away concerns about things like low-level threading, synchronization, thread-safety, concurrent data structures, and non-blocking I/O.

Reactive extensions have been implemented in many languages, also in Scala in project RxScala. What does it have to do with this post? This library makes heavy use of covariance and contravariance. Take look at `Observable` and `Observer` which I think are two most important types of this library. Those types are examined next and a new advanced concept called flipped classification is introduced.

#### Flipped classification

`Observable` is a type that produces values of type `T` and is covariant in that type parameter. However, if you look at method `subscribe` you might think that it uses type `T` in illegal position. After all, it was explained before that if type parameter is declared as covariant then it can be used as method argument type if it has a lower bound (`[B >: T]`). So the question is, why `subscribe` above compiles? The answer is flipped classification. Method `subscribe` accepts parametrized type `Observer` as an argument. The trick is that `Observer` is contravariant in its type parameter `T`.

Flipped classification also applies to `map` method of `Observable`. Method `map` accepts function `(T => R)` as an argument, that is `Function1[-T, +R]`. `Function1` is contravariant in type parameter `T` so flipped classification is also applied by the Scala compiler.

Flipped classification is explained in more detail in The fast track section of Type Parameterization chapter in Programming In Scala.

## Use-site and declaration-site variance

Only declaration-site variance has been described so far. It is defined during the declaration of the type with a + prefix for covariant type parameter and a - prefix for contravariant type parameter.

Another kind of variance is use-site variance which is defined by the user of the type. It is best explained with an example. `VendingMachine` below is invariant in its type parameter `A`.

If the user of the type `VendingMachine` would like to use covariant subtyping then he would have to define covariance himself using upper bound.

If the method `install` was defined as `install(softDrinkVM: VendingMachine[SoftDrink]): Unit` then code above wouldn't compile because it would have required the types to match exactly. That is, the method `install` would have accepted only values of type `VendingMachine[SoftDrink]`.

### Use-site variance readability and usage issues

Personally I think that in contrast to declaration-site variance, use-site variance makes code harder to read. Worst of all, use-site variance has to be often exposed in public API. Consider Java which only supports use-site variance for generics. Java 8 introduced lambdas and added a lot of new functional style types to its standard library. Those types often use covariance and contravariance to give their users more flexibility. The price of this flexibility is API that can be unpleasant to read. Listing below shows few example methods of new types added in Java 8. Return types are ommited.

In functional style programming it is very usual to have higher order functions, that is, functions that take function as an argument. In Java 8, everytime a higher order function is defined, the function taken as an argument should have use-site variance annotations: `Function<? super T,? extends K>`. This is really cumbersome but as Java programmers we have to live with it. Things would be much easier and more pleasant if Java featured declaration-site variance.

### Use-site variance may reduce functionality of the type

I believe that there is even a worse problem with use-site variance. Take a look at class `Box` defined in the next code listing. `Box` uses type parameter `A` as both output and input, so it can't be declared by the creator of the class as neither covariant nor contravariant.

Code below creates instances of `Box` of type `SoftDrink`. It puts `Cola` into it and then retrieves it.

If the user would have liked to use covariant subtyping with class `Box` then he would have to add variance annotations himself. However, this would have made method `put` no longer usable because it wouldn't be possible for the compiler to figure out the correct type of the argument of the method `put`.

On the other hand, if the user would have liked to use contravariant subtyping using use-site variance then he would have made the method `retrieve` mostly unusable. That is, any type safety would be gone. User could only retrieve something like `Any`.

Java programmers sometimes have to make a collection like `java.util.List` covariant or contravariant in its type parameter. The same issues as with `Box` class apply in this case.

The fact that use-site variance can make some functionality of the type completely unusable can suprise a lot of users (programmers). With declaration-site variance, Scala compiler makes sure that variance annotations are only used when it makes sense, that is, only if they add more flexibility for the user. Finally, declaration-site variance makes APIs and code much cleaner than use-site variance.

## Summary

It is important that both developers of types and their users understand covariance and contravariance. Correct use of variance makes types more flexible and lets their users achieve more functionality with less code.

From the perspective of type developer it is easiest to remember that covariant type parameter should be most often used as output type (in producers) and contravariant type parameter as input type (in consumers). If type parameter has to be used as both output and input type then it should be invariant. However, remember that there are exceptions, for example, covariant type parameter can be used as method argument type if lower bound is used.

From the perspective of type user it is best to remember rules below. First, covariant subtyping.

And next, contravariant subtyping which is the opposite of covariant subtyping.

If you forget rules above, try to remind yourself of vending machine and garbage can metaphors. Last of all, all code examples from this post and more are available at github.

## References

[Meijer2014] Meijer, Erik. Contravariance is the Dual of Covariance Implies Iterable is the Dual of Observable(Making Money Using Math), 2014.
<https://vimeo.com/98922027>

[Odersky2014] Odersky, Martin. Scala By Example, pages 56-58. 2014.
<http://www.scala-lang.org/docu/files/ScalaByExample.pdf>

[Odersky2008] Odersky, M., Parrow, J., Walker, D.: Programming in Scala: A comprehensive Step-by-step Guide. Artima Incorporation, 2008.
<http://www.artima.com/pins1ed/type-parameterization.html>

[Bloch2008] Bloch, Joshua. Effective Java: Second Edition. Addison-Wesley, Boston, 2008

[Reactivex.io] http://reactivex.io/intro.html

## Terms table

There are a lot of terms connected with covariance, contravariance and generics in general. Table below summarizes these terms. It contains a lot of terms and examples from [Bloch2008] and some new ones related to variance annotations.

Term Scala Example Java Example
Parametrized type `List[String]` `List<String>`
Actual type parameter `String` `String`
Generic type `List<A>` `List<E>`
Formal type parameter `A` `E```
Unbounded wildcard type `List[_]` `List<?>`
Raw type `List` `List`
Type parameter with lower bound `[A >: Number]` `<E super Number>`
Type parameter with upper bound `[A <: Number]` `<E extends Number>`
Wildcard type with lower bound `[_ >: Number]` `<? super Number>`
Wildcard type with upper bound `[_ <: Number]` `<? extends Number>`
Recursive type bound `[A <: Ordered[A]]` `<T extends Comparable<T>>`
Type constructor `List, constructs List[Int] etc` `Same as in Scala`
Variance annotation `+ or - i.e. [+A] or [-A]` `not supported`
Covariance annotation `+ i.e. [+A]` `not supported`
Contravariance annotation `- i.e. [-A]` `not supported`
Written on October 6, 2015