# Of variance and functors

by Adelbert Chang on Feb 04, 2016

technical

Scala’s type system allows us to annotate type parameters with their variance: covariant, contravariant, invariant. Variance allows us to define the subtyping relationships between type constructors – that is, under which conditions `F[A]` is a subtype of `F[B]`.

Similarly in functional programming, there are covariant functors, contravariant functors, and invariant functors. The similarity in names is not coincidental.

# Covariance

The common example is `List[+A]` which is covariant in its type parameter, denoted by the `+` next to the `A`. A type constructor with a covariant type parameter means that if there is a subtyping relationship between the type parameter, there is a subtyping relationship between the two instances of the type constructor. For example if we have a `List[Circle]`, we can substitute it anywhere we have a `List[Shape]`.

Another example of covariance is in parsing, for example in the following `Read` type class.

``````trait Read[+A] {
}
``````

It makes sense to make `Read` covariant because if we can read a subtype, then we can read the supertype by reading the subtype and throwing away the subtype-specific information. For instance, if we can read a `Circle`, we can read a valid `Shape` by reading the `Circle` and ignoring any `Circle`-specific information.

## Array

A type that cannot safely be made covariant is `Array`. If `Array` were covariant, we could substitute an `Array[Circle]` for an `Array[Shape]`. This can get us in a nasty situation.

``````val circles: Array[Circle] = Array.fill(10)(Circle(..))
val shapes: Array[Shape] = circles // works only if Array is covariant
shapes(0) = Square(..) // Square is a subtype of Shape
``````

If `Array` was covariant this would compile fine, but fail at runtime. In fact, Java arrays are covariant and so the analogous Java code would compile, throwing an `ArrayStoreException` when run. The compiler accepts this because it is valid to upcast an `Array[Circle]` into an `Array[Shape]`, and it is valid to insert a `Shape` into an `Array[Shape]`. However the runtime representation of `shapes` is still an `Array[Circle]` and inserting a `Square` into that isn’t allowed.

In general, a type can be made safely covariant if it is read-only. If we know how to read a specific type, we know how to read a more general type by throwing away any extra information. `List` is safe to to make covariant because it is immutable and we can only ever read information off of it. With `Array`, we cannot make it covariant because we are able to write to it.

## Functor

As we’ve just seen, covariance states that when `A` subtypes `B`, then `F[A]` subtypes `F[B]`. Put differently, if `A` can be turned into a `B`, then `F[A]` can be turned into an `F[B]`. We can encode this behavior literally in the notion of a `Functor`.

``````trait Functor[F[_]] {
def map[A, B](f: A => B): F[A] => F[B]
}
``````

This is often encoded slightly differently by changing the order of the arguments:

``````trait Functor[F[_]] {
def map[A, B](fa: F[A])(f: A => B): F[B]
}
``````

We can implement `Functor` for `List` and `Read`.

``````val listFunctor: Functor[List] =
new Functor[List] {
def map[A, B](fa: List[A])(f: A => B): List[B] = fa match {
case Nil => Nil
case a :: as => f(a) :: map(as)(f)
}
}

case None => None
case Some(a) => Some(f(a))
}
}
}
``````

With that we can do useful things like

``````val circles: List[Circle] = List(Circle(..), Circle(..))
val shapes: List[Shape] = listFunctor.map(circles)(circle => circle: Shape) // upcast

``````

or more generally:

``````def upcast[F[_], A, B <: A](functor: Functor[F], fb: F[B]): F[A] =
functor.map(fb)(b => b: A)
``````

`upcast`’s behavior does exactly what covariance does – given some supertype `A` (`Shape`) and a subtype `B` (`Circle`), we can mechanically (and safely) turn an `F[B]` into an `F[A]`. Put differently, anywhere we expect an `F[A]` we can provide an `F[B]`, i.e. covariance. For this reason, `Functor` is sometimes referred to in full as covariant functor.

# Contravariance

Contravariance flips the direction of the relationship in covariance – an `F[Shape]` is considered a subtype of `F[Circle]`. This seems strange – when I was first learning about variance I couldn’t come up with a situation where this would make sense.

If we have a `List[Shape]` we cannot safely treat it as a `List[Circle]` – doing so comes with all the usual warnings about downcasting. Similarly if we have a `Read[Shape]`, we cannot treat it as a `Read[Circle]` – we know how to parse a `Shape`, but we don’t know how to parse any additional information `Circle` may need.

## Show

It appears fundamentally read-only types cannot be treated as contravariant. However, given that contravariance is covariance with the direction reversed, can we also reverse the idea of a read-only type? Instead of reading a value from a `String`, we can write a value to a `String`.

``````trait Show[-A] {
def show(a: A): String
}
``````

`Show` is the other side of `Read` – instead of going from a `String` to an `A`, we go from an `A` into a `String`. This reversal allows us to define contravariant behavior – if we are asked to provide a way to show a `Circle` (`Show[Circle]`), we can give instead a way to show just a `Shape`. This is a valid substitution because we can show a `Circle` by throwing away `Circle`-specific information and showing just the `Shape` bits. This means that `Show[Shape]` is a subtype of `Show[Circle]`, despite `Circle` being a subtype of `Shape`.

In general, we can show (or write) a subtype if we know how to show a supertype by tossing away subtype-specific information (an upcast) and showing the remainder. Again, this means `Show[Supertype]` is substitutable, or a subtype of, `Show[Subtype]`.

## Array, again

`Array`s cannot be made contravariant either. If they were, we could do unsafe reads:

``````val shapes: Array[Shape] = Array.fill(10)(Shape(..), Shape(..))
val circles: Array[Circle] = shapes // Works only if Array is contravariant
val circle: Circle = circles(0)
``````

`circle`, having been read from an `Array[Circle]` has type `Circle`. To the compiler this would be fine, but at runtime, the underlying `Array[Shape]` may give us a `Shape` that is not a `Circle` and crash the program.

## Contravariant

Our `Functor` interface made explicit the behavior of covariance - we can define a similar interface that captures contravariant behavior. If `B` can be used where `A` is expected, then `F[A]` can be used where an `F[B]` is expected. To encode this explicitly:

``````trait Contravariant[F[_]] {
// Alternative encoding:
// def contramap[A, B](f: B => A): F[A] => F[B]

// More typical encoding
def contramap[A, B](fa: F[A])(f: B => A): F[B]
}
``````

We can implement an instance for `Show`.

``````val showContravariant: Contravariant[Show] =
new Contravariant[Show] {
def contramap[A, B](fa: Show[A])(f: B => A): Show[B] =
new Show[B] {
def show(b: B): String = {
val a = f(b)
fa.show(a)
}
}
}
``````

Here we are saying if we can show an `A`, we can show a `B` by turning a `B` into an `A` before showing it. Upcasting is a specific case of this, when `B` is a subtype of `A`.

``````def contraUpcast[F[_], A, B >: A](contra: Contravariant[F], fb: F[B]): F[A] =
contra.contramap(fb)((a: A) => a: B)
``````

Going back to `Shape`s and `Circle`s, we can show a `Circle` by upcasting it into a `Shape` and showing that.

# Function variance

We observed that read-only types are covariant and write-only types are contravariant. This can be seen in the context of functions and what function types are subtypes of others.

## Parameters

An example function:

``````// Right now we only care about the input
def squiggle(circle: Circle): Unit = ???

// or

val squiggle: Circle => Unit = ???
``````

What type is a valid subtype of `Circle => Unit`? An important note is we’re not looking for what subtypes we can pass in to the function, we are looking for a value with a type that satisfies the entirety of the function type `Circle => Unit`.

A first guess may involve some subtype of `Circle` like `Dot` (a circle with a radius of 0), such as `Dot => Unit`.

``````val squiggle: Circle => Unit =
(d: Dot) => d.someDotSpecificMethod()
``````

This doesn’t work – we are asserting with the moral equivalent of a downcast that any `Circle` input to the function is a `Dot`, which is not safe to assume.

What if we used a supertype of `Circle`?

``````val squiggle: Circle => Unit =
(s: Shape) => s.shapeshift()
``````

This is valid – from the outside looking in we have a function that takes a `Circle` and returns `Unit`. Internally, we can take any `Circle`, upcast it into a `Shape`, and go from there. Showing things a bit differently reveals better the relationship:

``````type Input[A] = A => Unit
val inputSubtype: Input[Shape] = (s: Shape) => s.shapeshift()
val input: Input[Circle] = inputSubtype
``````

We have `Input[Shape] <: Input[Circle]`, with `Circle <: Shape`, so function parameters are contravariant.

The type checker enforces this when we try to use covariant type parameters in contravariant positions.

``````scala> trait Foo[+A] { def foo(a: A): Int = 42 }
<console>:15: error: covariant type A occurs in contravariant position in type A of value a
trait Foo[+A] { def foo(a: A): Int = 42 }
^
``````

Since type parameters are contravariant, a type in that position cannot also be covariant. To solve this we “reverse” the constraint imposed by the covariant annotation by parameterizing with a supertype `B`.

``````scala> trait Foo[+A] { def foo[B >: A](a: B): Int = 42 }
defined trait Foo
``````

## Return

Let’s do the same exercise with function return types.

``````val squaggle: Unit => Shape = ???
``````

Since using the supertype seemed to work with parameters, let’s pick a supertype here, `Object`.

``````val squaggle: Unit => Shape =
(_: Unit) => somethingThatReturnsObject()
``````

For similar issues with using a subtype for the input parameter, we cannot use a supertype for the output. The function type states the return type is `Shape`, but we’re returning an `Object` which may or may not be a valid `Shape`. As far as the type checker is concerned, this is invalid and the checker rejects the program.

``````val squaggle: Unit => Shape =
(_: Unit) => Circle(..)
``````

This makes sense – the function type says it returns a `Shape` and inside we return a `Circle` which is a perfectly valid `Shape`.

As before, rephrasing the type signatures leads to some insights.

``````type Output[A] = Unit => A
val outputSubtype: Output[Circle] = (_: Unit) => Circle(..)
val output: Output[Shape] = outputSubtype
``````

That is `Output[Circle] <: Output[Shape]` with `Circle <: Shape` – function return types are covariant.

Again the type checker will enforce this:

``````scala> trait Bar[-A] { def bar(): A = ??? }
<console>:15: error: contravariant type A occurs in covariant position in type ()A of method bar
trait Bar[-A] { def bar(): A = ??? }
^
``````

As before, we solve this by “reversing” the contraint imposed by the variance annotation.

``````scala> trait Bar[-A] { def bar[B <: A](): B = ??? }
defined trait Bar
``````

## All together now

Function inputs are contravariant and function outputs are covariant. Taking the previous examples together, a function type `Shape => Circle` can be put in a place expecting a function type `Circle => Shape`.

We arrived at this conclusion by observing the behavior of subtype variance and the corresponding functors. Taken in the context of functional programming where the only primitive is a function, we can draw a conclusion in the other direction. Where function inputs are contravariant, types in positions where computations are done (e.g. input or read-only positions) are also contravariant (similarly for covariance).

# Invariance

Unannotated type parameters are considered invariant – the only relationship that holds is if a type `A` is equal to a type `B`, then `F[A]` is equal to `F[B]`. Otherwise different instantiations of a type constructor have no relationship with one another. Given invariant `F[_]`, an `F[Circle]` is not a subtype of `F[Shape]` – you need to explicitly provide the conversion.

## Array once more

`Array`s are invariant in Scala because they can be neither covariant nor contravariant. If we make it covariant, we can get unsafe writes. If we make it contravariant, we can get unsafe reads. Since read-only types can only be covariant and write-only types contravariant, our compromise is to make types that support both invariant.

In order to treat an `Array` of one type as an `Array` of another, we need to have conversions in both directions. This must be provided manually as the type checker has no way of knowing what the conversion would be.

## Invariant

Similar to (covariant) `Functor` and `Contravariant`, we can write `Invariant`.

``````trait Invariant[F[_]] {
def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B]
}
``````

For demonstration purposes we write our own `Array` type

``````class Array[A] {
private var repr = ListBuffer.empty[A]

repr(i)
def write(i: Int, a: A): Unit =
repr(i) = a
}
``````

and define `Invariant[Array]`.

``````val arrayInvariant: Invariant[Array] =
new Invariant[Array] {
def imap[A, B](fa: Array[A])(f: A => B)(g: B => A): Array[B] =
new Array[B] {
// Convert read A to B before returning – covariance
override def read(i: Int): B =

// Convert B to A before writing – contravariance
override def write(i: Int, b: B): Unit =
fa.write(i, g(a))
}
}
``````

## Serialization

Another example of a read-write type that doesn’t involve `Array`s (or mutation) can be found by just combining the `Read` and `Show` interfaces:

``````trait Serializer[A] extends Read[A] with Show[A] {
def show(a: A): String
}
``````

`Serializer` both reads (from a `String`) and writes (to a `String`). We can’t make it covariant because that would cause issues with `show`, and we can’t make it contravariant because that would cause issues with `read`. Therefore our only choice is to keep it invariant.

``````val serializerInvariant: Invariant[Serializer] =
new Invariant[Serializer] {
def imap[A, B](fa: Serializer[A])(f: A => B)(g: B => A): Serializer[B] =
new Serializer[B] {
def show(b: B): String = fa.show(g(b))
}
}
``````

# Bringing everything together

We can see the `Invariant` interface is more general than both `Functor` and `Contravariant` – where `Invariant` requires functions going in both directions, `Functor` and `Contravariant` only require one. We can make `Functor` and `Contravariant` subtypes of `Invariant` by ignoring the direction we don’t care about.

``````trait Functor[F[_]] extends Invariant[F] {
def map[A, B](fa: F[A])(f: A => B): F[B]

def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B] =
map(fa)(f)
}

trait Contravariant[F[_]] extends Invariant[F] {
def contramap[A, B](fa: F[A])(f: B => A): F[B]

def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B] =
contramap(fa)(g)
}
``````

Going back to treating `Array` and `Serializer` as a read/write store, if we make it read-only (like a read-only handle on a resource) we can safely treat it as if it were covariant. If we are asked to read `Shape`s and we know how to read `Circle`s, we can read a `Circle` and upcast it into a `Shape` before handing it over.

Similarly if we make it write-only (like a write-only handle on a resource) we can safely treat it as contravariant. If we are asked to store `Circle`s and we know how to store `Shape`s, we can upcast each `Circle` into a `Shape` before storing it.

Variance manifests in two levels: one at the type level where subtyping relationships are defined, and the other at the value level where it is encoded as an interface which certain types can conform to.

## One more thing

Thus far we have seen the three kinds of variances Scala supports:

``````1. invariance: A = B → F[A] = F[B]
2. covariance: A <: B → F[A] <: F[B]
3. contravariance: A >: B → F[A] <: F[B]
``````

This gives us the following graph:

``````   invariance
↑   ↑
/      \
-        +
``````

Completing the diamond implies a fourth kind of variance, one that takes contravariance and covariance together. This is known as phantom variance or anyvariance, a variance with no constraints on the type parameters: `F[A] = F[B]` regardless of what `A` and `B` are. Unfortunately Scala’s type system is missing this kind of variance which leaves us just short of a nice diamond, but we can still encode it in an interface.

``````trait Phantom[F[_]] {
def pmap[A, B](fa: F[A]): F[B]
}
``````

Given any `F[A]`, we can turn that into an `F[B]`, for all choices of `A` and `B`. With this power we can implement covariant and contravariant functors.

``````trait Phantom[F[_]] extends Functor[F] with Contravariant[F] {
def pmap[A, B](fa: F[A]): F[B]

def map[A, B](fa: F[A])(f: A => B): F[B] = pmap(fa)

def contramap[A, B](fa: F[A])(f: B => A): F[B] = pmap(fa)
}
``````

This completes our diamond of variance.

``````   invariance
↑   ↑
/      \
-        +
↑        ↑
\      /
phantom
``````