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.
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] {
def read(s: String): Option[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.
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.
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)
}
}
val readFunctor: Functor[Read] =
new Functor[Read] {
def map[A, B](fa: Read[A])(f: A => B): Read[B] =
new Read[B] {
def read(s: String): Option[B] =
fa.read(s) match {
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
val parseCircle: Read[Circle] = ...
val parseShape: Read[Shape] = readFunctor.map(parseCircle)(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 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.
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].
For similar reasons that read-only types can be made covariant, write-only types can be made contravariant.
Arrays 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.
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 Shapes and Circles, we can show a Circle by upcasting it into a Shape and showing that.
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.
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
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.
Trying instead with a subtype:
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
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).
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.
Arrays 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.
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]
def read(i: Int): 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 =
f(fa.read(i))
// Convert B to A before writing – contravariance
override def write(i: Int, b: B): Unit =
fa.write(i, g(a))
}
}
Another example of a read-write type that doesn’t involve Arrays (or mutation) can be
found by just combining the Read and Show interfaces:
trait Serializer[A] extends Read[A] with Show[A] {
def read(s: String): Option[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 read(s: String): Option[B] = fa.read(s).map(f)
def show(b: B): String = fa.show(g(b))
}
}
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
Shapes and we know how to read Circles, 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 Circles and we know how to store Shapes,
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.
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
