Developer Blog

Cheat Codes for Contravariance and Covariance

I used to have nightmares about understanding variance. I thought things would get better when someone showed me this explanation…

panda hiding in an oreo factory

(image from rice.edu)

…but afterwards the nightmares got worse, since now they included clowns and burning pandas. I stayed up for days.

The goal of this post is to help you become more familiar with variance so that it is easier to understand in code you are reading, and so that you can use it when appropriate. The goal is not to promote the usage of variance (or overusage). Variance is a tool that can be powerful, but keep in mind that most parameterized types you define will be invariant.

Note that if you already know what variance is, and you just want a quick reference to remind you how to tell the difference between co/contravariance, refer to the cheatsheet at the bottom of this post

Why do we even need variance?

Variance is how we determine if instances of parameterized types are subtypes or supertypes of one another. In a statically typed environment with subtyping and generics, this boils down to the compiler needing to determine when one type can be substituted for another type in an expression. For simple types, this is straightforward:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
trait Life

class Bacterium extends Life

trait Animal extends Life {
  def sound: String
}

class Dog(name: String, likesFrisbees: Boolean) extends Animal {
  val sound = "bark"
}

class Cat(name: String, likesHumans: Boolean) extends Animal {
  val sound = "meow"
}

def whatSoundDoesItMake(animal: Animal): String =
  animal.sound

A Dog is an Animal, and so is a Cat, so anything that expects an Animal can also take a Dog or Cat. This is a classic example of the Liskov substitution principle.

What are we really doing here though? We’re trying to determine when some type T can safely be substituted for a type U in an expression that expects a U. The expression that expects a U only cares that it gets a U for 2 reasons:

  • The expression calls methods on a U
  • The expression passes a U to another expression that expects a U

An expression that passes a U along eventually makes its way to an expression that does call methods on a U (or stores it for later method calling). So we’re left with only caring about whether something can be substited for another thing, because we want to make sure that it is safe to call methods on that thing (and by “safe” I mean “will never fail at runtime”). This is what we want our compiler to do: make sure that we never call the method something.sound on a type that does not have the method sound defined.

A wild variant appears

Looking at a type that has parameters, it is no longer obvious when substitution within an expression is allowed. In other words, if a function takes an argument of type ParametricType[T], is it safe to pass it a ParametricType[U]? This is what variance is all about.

Covariance

Container types are the best example of something that is covariant, so let’s look at an example:

1
2
3
4
5
6
7
8
9
10
11
12
val dogs: Seq[Dog] = Seq(
  new Dog("zoe", likesFrisbees = true),
  new Dog("james vermillion borivarge III", likesFrisbees = false)
)

val cats: Seq[Cat] = Seq(
  new Cat("cheesecake", likesHumans = true),
  new Cat("charlene", likesHumans = false)
)

def whatSoundsDoTheyMake(animals: Seq[Animal]): Seq[String] =
  animals map (_.sound)

Our method whatSoundsDoTheyMake expects a Seq[Animal], and it calls the method .sound on those animals. We know that all Animals have the method .sound defined on them, and we know that we are mapping over a list of Animals, so it’s totally OK to pass whatSoundsDoTheyMake a Seq[Dog] or a Seq[Cat].

Dog <: Animal implies Seq[Dog] <: Seq[Animal]

Notice where the method call on the animals actually happens. It doesn’t happen within the definition of Seq. Rather, it happens inside of a function that receives the Animal as an argument. Now consider what would happen if we tried to pass a Seq[Life] to whatSoundsDoTheyMake. First off, the compiler wouldn’t allow this because it’s unsafe: error: value sound is not a member of Life. If it were allowed though, then you could attempt to call bacterium.sound, even though the method doesn’t exist on that object. Note that in a dynamically typed language you could try to do this, but you’d get a runtime exception like TypeError: Object #<Bacterium> has no method 'sound'.

Interestingly, the real problem doesn’t occur within Seq; it occurs later on down the chain. The reason is that a generic type makes guarantees to other types and functions that it interacts with. Declaring a class as covariant on type T is equivalent to saying “if you call functions on me, and I provide you with an instance of my generic type T, you can be damn sure that every method you expect will be there”. When that guarantee goes away, all hell breaks loose.

Contravariance

Functions are the best example of contravariance (note that they’re only contravariant on their arguments, and they’re actually covariant on their result). For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Dachshund(
  name: String,
  likesFrisbees: Boolean,
  val weinerness: Double
) extends Dog(name, likesFrisbees)

def soundCuteness(animal: Animal): Double =
  -4.0/animal.sound.length

def weinerosity(dachshund: Dachshund): Double =
  dachshund.weinerness * 100.0

def isDogCuteEnough(dog: Dog, f: Dog => Double): Boolean =
  f(dog) >= 0.5

Should we be able to pass weinerosity as an argument to isDogCuteEnough? The answer is no, because the function isDogCuteEnough only guarantees that it can pass, at most specific, a Dog to the function f. When the function f expects something more specific than what isDogCuteEnough can provide, it could attempt to call a method that some Dogs don’t have (like .weinerness on a Greyhound, which is insane).

What about soundCuteness, can we pass that to isDogCuteEnough? In this case, the answer is yes, because even if isDogCuteEnough passes a Dog to soundCuteness, soundCuteness takes an Animal, so it can only call methods that all Dogs are guaranteed to have.

Dog <: Animal implies Function1[Animal, Double] <: Function1[Dog, Double]

A function that takes something less specific as an argument can be substituted in an expression that expects a function that takes a more specific argument.

Conclusion

Enforcing safety by following expression substitution rules for parameterized types is a complex but super useful tool. It constrains what we can do, but these are things that we shouldn’t do, because they can fail at runtime. Variance rules, and type safety in general, can be seen as a set of restrictions that force us to engineer solutions that are more robust and logically sound. It’s like how bones and muscles are a set of constraints that allow for extremely complex and functional motion. You’ll never find a boneless creature that can move like this:

extremely complex and functional motion

Cheatsheet

Here is how to determine if your type ParametricType[T] can/cannot be covariant/contravariant:

A type can be covariant when it does not call methods on the type that it is generic over. If the type needs to call methods on generic objects that are passed into it , it cannot be covariant.

Archetypal examples: Seq[+A], Option[+A], Future[+T]

A type can be contravariant when it does call methods on the type that it is generic over. If the type needs to return values of the type it is generic over, it cannot be contravariant.

Archetypal examples: Function1[-T1, +R], CanBuildFrom[-From, -Elem, +To], OutputChannel[-Msg]

Rest assured, the compiler will inform you when you break these rules:

1
2
3
4
5
6
7
8
9
10
11
trait T[+A] { def consumeA(a: A) = ??? }
// error: covariant type A occurs in contravariant position
//   in type A of value a
//       trait T[+A] { def consumeA(a: A) = ??? }
//                                  ^

trait T[-A] { def provideA: A = ??? }
// error: contravariant type A occurs in covariant position in
//  type => A of method provided
//       trait T[-A] { def provideA: A = ??? }
//                         ^

Comments