“Variance refers to how subtyping between more complex types relates to subtyping between their components” — Wikipedia
Types
A value is the result of an expression, a type is a set of values. Each value in our program has a type, and every type has a finite/infinite possible values. For instance:
- Boolean is a type that has two possible values:
true
orfalse
- String has infinite possible values.
- This sum type is a set of 3 values,
[Circle, Triangle, Rectangle]
sealed trait Shape
case object Circle extends Shape
case object Triangle extends Shape
case object Rectangle extends Shape
- Product type:
Container
has a combination of n values of typeShape
with m values of typeBoolean
→ 3 * 2 = 6 possible values.
case class Container(form: Shape, hasBg: Boolean)
Subtypes
Scala supports subtyping.
In our programming daily life, we encounter subtypes like:
Some
andNone
are subtypes ofOption
- In the previous example,
Circle, Triangle
andRectangle
are subtypes ofShape
Nothing
is the subtype of every type and there is no instances of this type.Any
is the supertype of every type in Scala. It’s the root of the Scala class hierarchy. So every type is a subtype ofAny
.
More complex types
A simple type:
case class Person(id: Int, name: String)
Person
is called a type constructor with 0 arity.
Kinds
It’s about how to classify the type constructors:
Person
is kind (star)*
the type constructor has no type parametersOption[A]
is kind (star to star):* -> *
becauseOption
has one parameterMap[K, V]
is kind (star star to star)* -> * -> *
Functor[F[_]]
is kind(* -> *) -> *
. This type is a higher kinded type, which takes a type constructorF
- There are more, you can check them in REPL using:
:kind -v TypeName
Variance annotation
Depending to the variance of the type constructor, the subtyping relation can be either preserved (covariance), reversed (contravariance), or ignored (invariance).
Covariance
Contravariance
Invariance
Function type
Let’s define a simple function:
scala> val addOne = (i: Int) => i + 1
addOne: Int => Int = <function1>
First class functions in Scala are implemented as FunctionX
classes. ( X
equals to the number of its argument)
In this example, we have a function with one parameter, the compiler picks Function1[Int, Int]
as the underlying typer.
Function1
has this type signature: Function[-A, +B]
-
and +
are variance annotations
Function[-A, +B]
is:
- Contravariant in the input type
A
(marked with-
) whereA
can be replaced with the derived type. (more general input argument) - Covariant in the output type
B
(marked with+
) whereB
can be replaced with the base type. (more specific return type)
Upper and Lower type bounds
Upper/Lower type bounds of a parameter type reveal more information about that type.
Upper type bounds: A <: T
means that A
refers to a subtype of T
Example:
abstract class Pet extends Animal {}
case class Cat(???) extends Pet
case class Dog(???) extends Pettrait Zoo[T <: Pet]{
...
}
Lower type bounds: A >: T
means that A
refers to a supertype of T
We will see an example soon.
In order to understand the previous sections, we need to see a simple example.
Let’s re-implement the type List
.
abstract class List[T] { ... }
case class Nil[T]() extends List[T]
case class Cons[T](head: T, tail: List[T]) extends List[T]
The type parameter at List
is not marked covariant or contravariant. So List
is invariant in T
which means List can only have elements of that type = T
cannot be changed.
sealed trait A
case object B extends A
case object C extends A
case object D extends A
If we want to define a list of type A that has elements of its subtypes we’ll get a compile error.
val list: List[A] = Cons(B, Cons(C, Cons(D, Nil()))) //compile error: class List is invariant in type A.
To make their dream come true, List
of the subtypes of A
should be represented as a List[A]
In simple types, we’re able to define: val a: A = B
But in HKT we have to add the variance annotation +
to the type parameter of our generic class List
to make it covariant in its type T
: List[+T]
abstract class List[+T] { ... }
case class Nil[T]() extends List[T]
case class Cons[+T](head: T, tail: List[T]) extends List[T]
Before checking if it works, let’s improve the case class Nil()
Every type T is a supertype of Nothing . List
is covariant in T
, so we can say that a List[Nothing]
is a subtype of List[T]
.
Nil
doesn’t use the type parameter, it could extends List[Nothing]
case object Nil extends List[Nothing]
Looks nicer!
val list: List[A] = Cons(B, Cons(C, Cons(D, Nil)))) //it works :)
Now let’s implement a function contains
in List
that checks if a given element exists.
abstract class List[+T] { self =>
def contains(elem: T): Boolean = self match {
case Cons(x, xs) if x == elem => true
case Cons(x, xs) => xs.contains(elem)
case Nil => false
}
}
Oups there is a compile error :
error: covariant type T occurs in contravariant position in type T of value elem
def contains(elem: T): Boolean = self match {
I talked previously about Function[-A, +B]
and mentioned that the inputs of functions are contravariant and their output are covariant. In our case, List
is covariant in T
,
The problem is in the input argument of contains
the element is a value of type T
which is covariant, we need to make it contravariant to be able to pass it into Function1
We can do that using lower type bounds >:
!
abstract class List[+T] { self =>
def contains[T1 >: T](elem: T1): Boolean = self match {
case Cons(x, xs) if x == elem => true
case Cons(x, xs) => xs.contains(elem)
case Nil => false
}
}
it works 😎 !
If you have a contravariant type parameter and you need to define a function that returns a value of that type, you’ll need to use the term <:
to make the output covariant.
I hope that you enjoyed reading this blog and now you’ll not worry when you see [+T],[-T], <:, >:
in code.