Variances in Scala by Wiem Zine El Abidine

scala> val addOne = (i: Int) => i + 1
addOne: Int => Int = <function1>

Following this rule:

“Be conservative in what you do, be liberal in what you accept from others” — robustness principle

 

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 Pet

trait 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.

 

This article was written by Wiem Zine El Abidine and posted originally on Medium.