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].
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.
install accepts a
VendingMachine of type
SoftDrink or subtypes of
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
TonicWater are subtypes of
VendingMachine of type
Drink can't be passed to the method
Drink is a supertype of
SoftDrink. That would be contravariant subtyping. Contravariance is explained later.
To sum up.
A is a subtype of
VendingMachine[A] should be a subtype of
VendingMachine[B]. This property is called covariant subtyping [Odersky2014].
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.
objects would be modified with value of type other than
ArrayStoreException would be thrown.
Scala fixes this problem by making its Array type invariant in its type parameter.
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.
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
Cola, so the method
addAll above returns instance of
VendingMachine of 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.
AmmoMagazine is used in the
Gun has method
reload which thanks to the covariant subtyping can be reloaded with both
AmmoMagazine[ExplosiveBullet], and in general with
AmmoMagazine of any subtype of
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.
setGarbageCanForPlastic accepts a
GarbageCan of type
PlasticItem or supertype of
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
GarbageCan of type
PlasticBottle can't be passed to the method
PlasticBottle is the subtype of
PlasticItem. That would be covariant subtyping.
To sum up.
A is a subtype of
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.
isVintage can be used to filter both
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
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.
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
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.
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
Flipped classification also applies to
map method of
map accepts function
(T => R) as an argument, that is
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
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
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
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
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.
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.
[Meijer2014] Meijer, Erik. Contravariance is the Dual of Covariance Implies Iterable is the Dual of Observable(Making Money Using Math), 2014.
[Odersky2014] Odersky, Martin. Scala By Example, pages 56-58. 2014.
[Odersky2008] Odersky, M., Parrow, J., Walker, D.: Programming in Scala: A comprehensive Step-by-step Guide. Artima Incorporation, 2008.
[Bloch2008] Bloch, Joshua. Effective Java: Second Edition. Addison-Wesley, Boston, 2008
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|
|Actual type parameter||
|Formal type parameter||
|Unbounded wildcard type||
|Type parameter with lower bound||
|Type parameter with upper bound||
|Wildcard type with lower bound||
|Wildcard type with upper bound||
|Recursive type bound||