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.

diagram

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.

class VendingMachine[+A] {
  // .. don't worry about implementation yet
}

def install(softDrinkVM: VendingMachine[SoftDrink]): Unit = {
  // Installs the soft drink vending machine
}

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.

// covariant subtyping
install(new VendingMachine[Cola])
install(new VendingMachine[TonicWater])
// invariant
install(new VendingMachine[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.

// Compile error ! contravariant subtyping
install(new VendingMachine[Drink])

To sum up.

// Covariant subtyping
               A  <:                B
VendingMachine[A] <: VendingMachine[B]

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.

Object[] objects = new String[] { "abc" };

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

String[] strings = { "abc" };
Object[] objects = strings;
// OOPS! Line below throws runtime exception: ArrayStoreException.
// Reason is that objects is actually an instance of 
// Array of Strings and we try to update it with an Integer.
objects[0] = 1;

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

// Simplified Array from Scala
final class Array[T](_length: Int) {
  // arr.update(i, x) is equivalent to arr(i) = x
  def update(i: Int, x: T): Unit = ...
  // ...
}

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.

class VendingMachine[+A](val currentItem: Option[A], items: List[A]) {

  def this(items: List[A]) = this(None, items)

  def dispenseNext(): VendingMachine[A] =
    items match {
      case Nil => {
        if (currentItem.isDefined)
          new VendingMachine(None, Nil)
        else
          this
      }
      case t :: ts => {
        new VendingMachine(Some(t), ts)
      }
    }

  def addAll[B >: A](newItems: List[B]): VendingMachine[B] =
    new VendingMachine(items ++ newItems)

}

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.

val colasVM: VendingMachine[Cola] = 
                    new VendingMachine(List(new Cola, new Cola))
val softDrinksVM: VendingMachine[SoftDrink] = 
                    colasVM.addAll(List(new TonicWater))

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.

trait Bullet
class NormalBullet extends Bullet
class ExplosiveBullet extends Bullet

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.

final class AmmoMagazine[+A <: Bullet](
    private[this] var bullets: List[A]) {
    
  def hasBullets: Boolean = !bullets.isEmpty

  def giveNextBullet(): Option[A] =
    bullets match {
      case Nil => {
        None
      }
      case t :: ts => {
        bullets = ts
        Some(t)
      }
    }
    
}

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.

final class Gun(private var ammoMag: AmmoMagazine[Bullet]) {

  def reload(ammoMag: AmmoMagazine[Bullet]): Unit =
    this.ammoMag = ammoMag  

  def hasAmmo: Boolean = ammoMag.hasBullets

  /** Returns Bullet that was shoot or None if there is ammo left */
  def shoot(): Option[Bullet] = ammoMag.giveNextBullet()

}
val gun = new Gun(AmmoMagazine.newNormalBulletsMag)
// compiles because of covariant subtyping
gun.reload(AmmoMagazine.newExplosiveBulletsMag)  

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.

diagram

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.

class GarbageCan[-A] {
  // .. don't worry about implementation yet
}

def setGarbageCanForPlastic(gc: GarbageCan[PlasticItem]): Unit = {
  // sets garbage can for PlasticItem items
}

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.

// contravariant subtyping
setGarbageCanForPlastic(new GarbageCan[Item])

// invariant
setGarbageCanForPlastic(new GarbageCan[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.

// Compile error ! covariant subtyping
setGarbageCanForPlastic(new GarbageCan[PlasticBottle])

To sum up.

// Contravariant subtyping
           A  <:            B
GarbageCan[B] <: GarbageCan[A]

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.

class GarbageCan[-A] {

  // compiles because of object private scope
  private[this] var items: List[A] = List.empty

  def put(item: A): Unit = this.items :+= item

  def putAll(items: List[A]): Unit = this.items ++= items

  def itemsCount: Int = this.items.size

}

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.

// a bit simplified source code from Scala API
trait Function1[-T, +R] extends AnyRef { 
  def apply(v1: 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.

trait MusicInstrument {
  val productionYear: Int
}
case class Guitar(productionYear: Int) extends MusicInstrument   
case class Piano(productionYear: Int) extends MusicInstrument

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

val isVintage: (MusicInstrument => Boolean) = _.productionYear < 1980

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.

val isVintage: (MusicInstrument => Boolean) = _.productionYear < 1980

test("should filter vintage guitars") {
  // given
  val guitars: List[Guitar] = List(new Guitar(1966), new Guitar(1988))
  // when
  val vintageGuitars: List[Guitar] = guitars.filter(isVintage)
  // then
  assert(List(new Guitar(1966)) === vintageGuitars)
}

test("should filter vintage pianos") {
  // given
  val pianos: List[Piano] = List(new Piano(1975), new Piano(1985))
  // when
  val vintagePianos: List[Piano] = pianos.filter(isVintage)
  // then
  assert(List(new Piano(1975)) === vintagePianos)
}

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.

def getPrices(instruments: List[MusicInstrument]) = {
  // returns prices of instruments    
}

val guitars: List[Guitar] = List(new Guitar(1966), new Guitar(1988))  
// covariant subtyping because Guitar is a subtype of MusicInstrument
val guitarsPrices = getPrices(guitars)

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

// very simiplified version of Observable
trait Observable[+T] {  
  def subscribe(observer: Observer[T]): Subscription  
  def map[R](func: T => R): Observable[R]  
  // much more  
}

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.

// simplified version of Observer
trait Observer[-T] {
  def onNext(value: T): Unit  
  // .. more methods
}

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.

class VendingMachine[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.

def install(softDrinkVM: VendingMachine[_ <: SoftDrink]): Unit = {
  // Installs soft drink vending machine
}
// covariant subtyping
install(new VendingMachine[Cola])

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.

// from CompletableFuture
thenCombine(
  CompletionStage<? extends U> other,
  BiFunction<? super T,? super U,? extends V> fn)
    
// from Collectors
groupingBy(
  Function<? super T,? extends K> classifier, 
  Collector<? super T,A,D> downstream)
toMap(
  Function<? super T,? extends K> keyMapper, 
  Function<? super T,? extends U> valueMapper)
  
// from Function
compose(Function<? super V,? extends T> before)

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.

class Box[A]() {

  private var thing: A = _
  
  def retrieve: A = thing
  
  def put(thing: A) = this.thing = thing
  
}

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

val softDrinkBox: Box[SoftDrink] = new Box()
softDrinkBox.put(new Cola)
val softDrink: SoftDrink = box.retrieve

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.

val softDrinkBox: Box[_ <: SoftDrink] = new Box()
// type mismatch; found : Cola required: _$4
// softDrinkBox.put(new Cola)
val softDrink: SoftDrink = softDrinkBox.retrieve

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.

val softDrinkBox: Box[_ >: SoftDrink] = new Box()
softDrinkBox.put(new Cola)
// can't retrieve and assign to type SoftDrink 
val softDrinkMaybe: Any = softDrinkBox.retrieve

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.

// you can't put elements into numbersCov but only retrieve them
final java.util.List<? extends Number> numbersCov = getCovList();
// only null can be put in
numbersCov.add(null);
final Number n = numbersCov.get(0);

// you can put elements into numbersContr but can't retrieve them
final java.util.List<? super Number> numbersContr = getContrList();
numbersContr.add(5);
// can be only assigned to Object
final Object o = numbersContr.get(0);

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.

// Covariant subtyping (Vending machine metaphore)
               A  <:                B
VendingMachine[A] <: VendingMachine[B]

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

// Contravariant subtyping (Garbage can metaphore)
           A  <:            B
GarbageCan[B] <: GarbageCan[A]

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