Variance in Scala

When we want to factorize common behaviors, we can rely on generics (also known as type constructors or parametric polymorphic types).
The Scala language allows us to be very specific about subtyping relationship between them... let's dive in what is called variance after a quick tour about type constructors.

Type constructor

A type constructor is declared by suffixing a type with the list of generic types wrapped by square brackets.

For a given type constructor F[T]:

• F is here the type constructor
• T represents the generic part and is called type parameter.

We usually pronounce it "F of T".

It is called type constructor because it will finally "construct" concrete types (also called parametrized types) such as F[Int] or F[String].

Type constructors may have many type parameters separated by commas, e.g.: F[A, B, C].

A lot of Scala well-known types are type constructors, e.g.: List, Option, Try, Either and even Function !

Variance

Actually, variance notion is closely related to the Liskov Substitution Principle (the "L" in the famous "S.O.L.I.D" acronym) which tells us:

If S is a subtype of T, then objects of type T may be replaced with objects of type S

We can thus wonder how it would work for type constructors... for instance, the type Int is a subtype of AnyVal, but according to our needs, what whould be the subtyping relationship between F[Int] and F[AnyVal] ?

First, let's discover the 3 kinds of variance that could be defined by adding (or not) variance annotations:
the + or - symbols before a type parameter:

• Invariance: F[T]
• Covariance: F[+T]
• Contravariance: F[-T]

For all examples we will use (by importing them):

• A 3 types hierarchy into the HumanResources object

object HumanResources {    class Employee(val name: String)    class TechEmployee(override val name: String) extends Employee(name)    case class Developer(override val name: String, favoriteLanguage: String) extends TechEmployee(name)}

• Some values from HumanResources

import HumanResources._// Employeesval bob = new Employee("Bob")val jane = new Employee("Jane")val alfred = new Employee("Alfred")val cassie = new Employee("Cassie")// More specific employees: Tech Employeesval jeremy = new TechEmployee("Jeremy")val alex = new TechEmployee("Alex")// Very specific employees: Developersval luc = Developer("Luc", "Scala")val alice = Developer("Alice", "Go")

Invariance

Definition

Invariance — which means "no variance" — for a type constructor F and a type parameter T is noted F[T].
It is used when we do not want neither supertypes nor subtypes of T share any of their subtyping relationship with F[T].

N.B: It is the default used variance as it does not require any annotation.

Example

As an example, we will create a meeting that should be capable to "gather" with another one.
Let's create a generic Meeting and a few kinds of meetings as subtypes...

Considering an invariant type constructor Meeting with a type parameter T: class Meeting[T], then neither Meeting[Employee] nor Meeting[Developer] and nor Meeting[TechEmployee] will have any subtyping relationship between them.

object InvarianceExample {    import HumanResources._    // Meeting is declared as an invariant type constructor    class Meeting[T](val name: String, val attendees: List[T]) {        def gather(otherMeeting: Meeting[T]): Meeting[T] = new Meeting[T](            s"$name & ${otherMeeting.name}" ,            (attendees ++ otherMeeting.attendees).toSet.toList        )    }    case class CompanyBreak(override val attendees: List[Employee])        extends Meeting[Employee]("Company Break", attendees)    case class Convention(override val attendees: List[Employee])        extends Meeting[Employee]("Convention", attendees)    case class DeveloperTraining(override val attendees: List[Developer])        extends Meeting[Developer]("Developer Training", attendees)}import InvarianceExample._val companyBreak = CompanyBreak(List(bob, jane))val convention = Convention(List(bob, alfred, cassie))// Will compile: we can gather 2 meetings of Employeesval allEmployeeMeetings = companyBreak.gather(convention) // : Meeting[Employee]val devTraining = DeveloperTraining(List(alice, luc))// Won't compile because of the invarianceval allMeetings = allEmployeeMeetings.gather(devTraining)

As we can see in InvarianceExample, we can verify at compilation time that only the exact same type is allowed as type parameter than the one expected: gathering a Meeting[Employee] with a Meeting[Developer] is not possible.

What if we play with variance annotations ? Let's see what happens if we prefix the type parameter with either a + (i.e.: Covariance ) or a - (i.e.: Contravariance)...

Covariance

Definition

The word "covariance" is composed by a prefix "co" — coming from Latin and meaning "with" — before the word "variance", and literally means "which vary with", or in our case: "which vary in the same way" than the type parameter.

If S is a subtype of T, then, given a covariant type constructor F, F[S] will be a subtype of F[T]

Covariance for a type constructor F and a type parameter T is noted F[+T].

Example

Considering a covariant type constructor Meeting with a type parameter +T: class Meeting[+T], then Meeting[Developer] will be considered as a subtype of Meeting[TechEmployee] (and also of Meeting[Employee]).

Thus, according to the Liskov Substitution Principle:

• Meeting[Developer] can replace an expected Meeting[TechEmployee] or an expected Meeting[Employee]
• Meeting[TechEmployee] can replace an expected Meeting[Employee]

Let's add the + variance annotation to the type constructor Meeting[T] of the previous InvarianceExample and see what happens when compiling...

object AddingCovarianceExample {    import HumanResources._    // Meeting is declared as a covariant type constructor    class Meeting[+T](val name: String, val attendees: List[T]) {       def gather(otherMeeting: Meeting[T]): Meeting[T] = new Meeting[T](            s"$name & ${otherMeeting.name}" ,            (attendees ++ otherMeeting.attendees).toSet.toList        )    }    case class CompanyBreak(override val attendees: List[Employee])        extends Meeting[Employee]("Company Break", attendees)    case class Convention(override val attendees: List[Employee])        extends Meeting[Employee]("Convention", attendees)    case class DeveloperTraining(override val attendees: List[Developer])        extends Meeting[Developer]("Developer Training", attendees)}

A new compilation error tells us:
covariant type T occurs in contravariant position in type Meeting[T] of value otherMeeting.

Actually, it makes sense: if we try to gather a Meeting[Employee] with a Meeting[Developer], what would be the concrete type parameter obtained when producing the new meeting ?
The only acceptable answer is the common ancestor of an Employee and Developer, which is... Employee !

Thus, in order to get rid of the compilation error, we have to specify that the function gather can only accept the generic T or one of its supertype (i.e: the common ancestor):

class Meeting[+T](val name: String, val attendees: List[T]) {   def gather(otherMeeting: Meeting[T]): Meeting[T] = new Meeting[T](   def gather[S >: T](otherMeeting: Meeting[S]): Meeting[S] = new Meeting[S](        s"$name & ${otherMeeting.name}" ,        (attendees ++ otherMeeting.attendees).toSet.toList    )}

Type Bounds

The notation [S >: T] is called lower type bound. It constrains the generic type S to be a supertype of type T (previously declared in the scope), or at least the exact same type (i.e.: T).

The converse type bound [S <: T] is called upper type bound and constrains S to be a subtype of T or a T.

It is possible to mix both variance annotations and type bounds: in our example it would be advised to add a such constraint on the Meeting type constructor, else we could be able to create meetings of Ints such as: new Meeting[Int]("Int meeting", List(1, 2, 3)).

In our context (Meeting of HR) this type is not generic enough to deal with a mere T and then we can constrain T to be an Employee or one of its subtype:

class Meeting[+T](val name: String, val attendees: List[T]) {  def gather[S >: T](otherMeeting: Meeting[S]): Meeting[S] = new Meeting[S](class Meeting[+T <: Employee](val name: String, val attendees: List[T]) {  def gather[S >: T <: Employee](otherMeeting: Meeting[S]): Meeting[S] = new Meeting[S](        s"$name & ${otherMeeting.name}" ,        (attendees ++ otherMeeting.attendees).toSet.toList    )}

N.B: we also must add the constraint everywhere T is used inside the class.

The full working example is now:

object CovarianceWithTypeBoundsExample {    import HumanResources._    // Meeting is declared as a covariant type constructor with a type bound    class Meeting[+T <: Employee](val name: String, val attendees: List[T]) {        def gather[S >: T <: Employee](otherMeeting: Meeting[S]): Meeting[S] = new Meeting[S](            s"$name & ${otherMeeting.name}" ,            (attendees ++ otherMeeting.attendees).toSet.toList        )    }    case class CompanyBreak(override val attendees: List[Employee])        extends Meeting[Employee]("Company Break", attendees)    case class Convention(override val attendees: List[Employee])        extends Meeting[Employee]("Convention", attendees)    case class DeveloperTraining(override val attendees: List[Developer])        extends Meeting[Developer]("Developer Training", attendees)}import CovarianceWithTypeBoundsExample._val companyBreak = CompanyBreak(List(bob, jane))val convention = Convention(List(bob, alfred, cassie))val allEmployeeMeetings = companyBreak.gather(convention) // : Meeting[Employee]val devTraining = DeveloperTraining(List(alice, luc))// Will now compile thanks to the covariance of Meetingval allMeetings = allEmployeeMeetings.gather(devTraining) // : Meeting[Employee]// Won't compile thanks to the type boundsval intMeeting = new Meeting[Int]("Int meeting", List(1, 2, 3))val meetingsWithInts = allEmployeeMeetings.gather(intMeeting)

Modeling business rules relying on types is a good practice called type-driven design, it allows us to check them directly at compilation time and help us making illegal states unrepresentables.

Contravariance

Definition

The word "contravariance" is composed by a prefix "contra" — coming from Latin and meaning "against" — before the word "variance", and literally means "which vary against", or in our case: "which vary in the opposite way" than the type parameter (cf. Liskov Substitution Principle).

If S is a subtype of T, then, given a contravariant type constructor F, F[S] will be a subtype supertype of F[T]

Contravariance for a type constructor F and a type parameter T is noted F[-T].

Example

An example to illustrate contravariance would be first to define an invariant type constructor Welcoming[T] with a function welcome(t: T): Unit taking the generic type as parameter.

abstract class Welcoming[T] {    def welcome(t: T): Unit}

And then we can create 2 Welcoming subclasses for welcoming differently either an Employee or a Developer. And also a companion object for our Welcoming[T] type constructor, the object named Welcoming with a generic constructor apply[T] which would automatically perform the welcoming.

object ContravarianceDraftExample {    import HumanResources._    abstract class Welcoming[T] {        def welcome(t: T): Unit    }    // Companion object of abstract class Welcoming[T]    object Welcoming {        def apply[T](t: T, welcoming: Welcoming[T]): Unit =            welcoming.welcome(hr)    }    // Custom subclasses for diffferent welcoming    class EmployeeWelcoming extends Welcoming[Employee] {       def welcome(t: Employee): Unit =             println(s"Welcome in our company ${t.name} !")    }    class DeveloperWelcoming extends Welcoming[Developer] {        def welcome(t: Developer): Unit =            println(                s"Welcome in our company <${t.name}>, happy coding in ${t.favoriteLanguage} !"            )    }}import ContravarianceDraftExample._val employeeWelcoming = new EmployeeWelcomingval developerWelcoming = new DeveloperWelcoming// Will print: "Welcome in our company Luc !"Welcoming[Employee](Developer("Luc", "Scala"), employeeWelcoming)// Will print: "Welcome in our company <Luc>, happy coding in Scala !"Welcoming[Developer](Developer("Luc", "Scala"), developerWelcoming)// Won't compile unless Welcoming[T] becomes contravariant and print: // "Welcome in our company Luc !"Welcoming[Developer](Developer("Luc", "Scala"), employeeWelcoming)

A Welcoming[Developer] needs a DeveloperWelcoming instance, as our Welcoming type constructor is invariant for the moment. It means it cannot welcome with an EmployeeWelcoming provided instance (cf. L42).

Does it mean there is no chance an EmployeeWelcoming be used to welcome a Developer ?

Actually, it doesn't ! It would just perform the welcome considering the Developer is just an Employee.

Let's add the - variance annotation to the type constructor Welcoming[T] of the previous ContravarianceDraftExample and see what happens when compiling...

Considering a contravariant type constructor Welcoming with a type parameter -T: abstract class Welcoming[-T], then, according to the Liskov Substitution Principle:

• Welcoming[Employee] can replace an expected Welcoming[TechEmployee] or an expected Welcoming[Developer]
• Welcoming[TechEmployee] can replace an expected Welcoming[Developer]

object ContravarianceExample {    import HumanResources._   abstract class Welcoming[T] {   abstract class Welcoming[-T] {        def welcome(t: T): Unit    }    object Welcoming {        def apply[T](t: T, welcoming: Welcoming[T]): Unit =            welcoming.welcome(hr)    }    class EmployeeWelcoming extends Welcoming[Employee] {       def welcome(t: Employee): Unit =             println(s"Welcome in our company ${t.name} !")    }    class DeveloperWelcoming extends Welcoming[Developer] {        def welcome(t: Developer): Unit =            println(                s"Welcome in our company <${t.name}>, happy coding in ${t.favoriteLanguage} !"            )    }}import ContravarianceExample._val employeeWelcoming = new EmployeeWelcomingval developerWelcoming = new DeveloperWelcoming// Will print: "Welcome in our company Luc !"Welcoming[Employee](Developer("Luc", "Scala"), employeeWelcoming)// Will print: "Welcome in our company <Luc>, happy coding in Scala !"Welcoming[Developer](Developer("Luc", "Scala"), developerWelcoming)// Now compile and print: "Welcome in our company Luc !"Welcoming[Developer](Developer("Luc", "Scala"), employeeWelcoming)

Now, welcoming a developer with an employee welcoming is possible.

But we can still create odd things such as:

class IntWelcoming extends Welcoming[Int] {    def welcome(t: Int): Unit = println(s"Haha, I'm an integer: $t !")}val intWelcoming = new IntWelcomingWelcoming[Int](1, intWelcoming)

In order to encode properly business rules and add programming good practice, let's add some type bounds and some important keywords.

Considering the business rules are locked, it would give:

object ContravarianceLockedExample {    import HumanResources._   abstract class Welcoming[-T] {       def welcome(t: T): Unit   private[ContravarianceLockedExample] abstract class Welcoming[-T <: Employee] {       protected def welcome(t: T): Unit    }    // Companion object of abstract class Welcoming[T]    object Welcoming {       def apply[T](t: T, welcoming: Welcoming[T]): Unit =       def apply[T <: Employee](t: T, welcoming: Welcoming[T]): Unit =            welcoming.welcome(hr)    }    // Custom subclasses for diffferent welcoming   class EmployeeWelcoming extends Welcoming[Employee] {      def welcome(t: Employee): Unit =    case object EmployeeWelcoming extends Welcoming[Employee] {      protected final def welcome(t: Employee): Unit =            println(s"Welcome in our company ${t.name} !")    }   class DeveloperWelcoming extends Welcoming[Developer] {       def welcome(t: Developer): Unit =   case object DeveloperWelcoming extends Welcoming[Developer] {       protected final def welcome(t: Developer): Unit =            println(                s"Welcome in our company <${t.name}>, happy coding in ${t.favoriteLanguage} !"            )    }}import ContravarianceLockedExample._val employeeWelcoming = new EmployeeWelcomingval developerWelcoming = new DeveloperWelcomingval employeeWelcoming = EmployeeWelcomingval developerWelcoming = DeveloperWelcoming// Will print: "Welcome in our company Luc !"Welcoming[Employee](Developer("Luc", "Scala"), employeeWelcoming)// Will print: "Welcome in our company <Luc>, happy coding in Scala !"Welcoming[Developer](Developer("Luc", "Scala"), developerWelcoming)// Will print: "Welcome in our company Luc !"Welcoming[Developer](Developer("Luc", "Scala"), employeeWelcoming)

The Welcoming class has now a generic type constraint according to domain rules, and is now only extendable within ContravarianceLockedExample object.

Handmade variance verification

If we want to type-check ourselves a type constructor variance, in order to help us we can play with:

• generic types aliases type F[A] = //...
• the infix class <:< along with its implicit evidence, which witnesses subtype relationship between 2 types
• type composition (with keyword)
• implicitly[T] parameterized function
• the compiler :)

class Superclass Sub extends Superclass Invariant[T]class Covariant[+T]class Contravariant[-T]type IsCovariant[F[_], SuperType, SubType] =    (SubType <:< SuperType)    with F[SubType] <:< F[SuperType]type IsContravariant[F[_], SuperType, SubType] =    (SubType <:< SuperType)    with F[SuperType] <:< F[SubType]// Checking an invariant type constructorimplicitly[IsCovariant[Invariant, Super, Sub]]implicitly[IsContravariant[Invariant, Super, Sub]]// Checking a covariant type constructorimplicitly[IsCovariant[Covariant, Super, Sub]]implicitly[IsContravariant[Covariant, Super, Sub]]// Switching the supertype and the subtype positions works !implicitly[IsContravariant[Covariant, Sub, Super]]// Checking a contravariant type constructor implicitly[IsCovariant[Contravariant, Super, Sub]]// Switching the supertype and the subtype positions works !implicitly[IsCovariant[Contravariant, Sub, Super]]implicitly[IsContravariant[Contravariant, Super, Sub]]// Checking a commonly used type constructor: List (which is covariant)implicitly[IsCovariant[List, AnyVal, Int]]implicitly[IsCovariant[List, Int, AnyVal]]implicitly[IsContravariant[List, AnyVal, Int]]implicitly[IsContravariant[List, Int, AnyVal]]

Caveats

I recently stumbled upon a ZIO Prelude issue about the behavior of a contravariant type constructor when an implicit instance is created among other ones, for the Scala bottom type Nothing.
It led me to a part of the Blue book (Functional Programming for Mortals by Sam Halliday) talking about variance.
The contravariant issue will be fixed in Dotty (aka Scala 3). But for covariant types, it's worth being aware that:

The problem with covariant type parameters, such as class List[+A], is that List[A] is a subtype of List[Any] and it is easy to accidentally lose type information.

As the concrete type infered by covariance is the first common supertype of the two concerned types, it may be the Scala top type Any.

For instance, a list of integers and strings:

List(1, "A", 2, "B") // : List[Any] = List(1, "A", 2, "B")

When creating your own covariant classes, do not hesitate to use type bounds to constrain it to fit the business rules.

That's all folks !

I hope you appreciated reading my very first technical post.
Do not hesitate to contact me if you have a question about it.

Thank you !