# Scala: Variance, Covariance, and Contravariance

### Introduction
This lesson will explain the different types of variance relations.

Given a generic type `G[T]`, where `T` is the type parameter, and given a type `B` and its subtype `A`, variance describes the relation between `G[A]` and `G[B]`. If there is no relation between between `G[A]` and `G[B]`, then `T` is invariant. If `G[A]` is a subtype of`G[B]`, then `T` is covariant. If `G[A]` is a supertype of`G[B]`, then `T` is contravariant. Notice, the type of variance is a property of the type parameter and not the generic classes themselves.

The concepts of variance, covariance, and contravariance belong to type theory and thus serveral languages support these concepts. However, for this report, variance relations will be studied through the perspective of Scala.
### Scala Overview
[comment]: # (Discuss types and classes, as well as the difference between the two. When referring to Complex types and Component types, use the definitions in the notes. I think it'd make sense to include Generics in Scala as a brief introduction)

Scala is a strong, statically typed language that supports object-oriented programming, functional programming, and is often run on a Java Virtual Machine (JVM). Scala was designed to be concise, and many of its design decisions were made to address criticisms of Java. Some of these features include functional programming features such as currying and pattern matching, as well as non-functional programming features like operator overloading and optional parameters.

A pre-requsite for understanding variance is understanding generics, which are classes or traits (Scala's more flexible version of Java's interface) that take in a type parameter.

The following of are examples of generics:

class ClassGeneric[C]
class MultiParamClassGeneric[A,B,C]
trait TraitGeneric[T]

There are also built-in generics:

val listGeneric1 : List[Int] = null
val listGeneric2 : List[Any] = List(1, 9.2, "A")

[comment]: # (Regarding code snippets, since we need two for each, I think it would make sense to give one example and one counter-example for each)
### Variance

[comment]: # (Review this section after we figure out the difference between types and classes)

Variance refers to the way that subtyping relationships of generic types (also called complex types) and their parameter types (also called component types) relate. In essence, it describes the correlation between the inheritance relationships of a generic class and its derived classes, and the inheritance relationships of its parameter class and its derived classes. The existence of variance in Scala allows for developers to have additional information about the subtyping relationship of parameter types, and make abstractions on generic types with hierarchically related parameters.

There are three types of variance relationships in Scala, covariance, contravariance, and invariance.

### Covariance

For some parameter type `T`, a generic class is made covariant using the annotation `+T`. For some generic class, making its parameter type covariant implies that for two types `A`, `B`, if `B` is a subtype of `A`, then the generic class with parameter `B` is a subtype of the generic class with parameter `A`.

We will consider the following example.

class Food(val name: String)
class Vegetable(override val name: String) extends Food(name) 
class GreenVeggie(override val name: String) extends Vegetable(name) 

In this example, `Food` is a class such that `Vegetable` is a child class of `Food`, and `GreenVeggie` is a child class of `Vegetable`.

// Definition of a trait.
trait Recipe[+A] {
  def ingredients: List[A]
}

// Class definitions that extend Recipe
class GenericRecipe(val ingredients: List[Food]) extends Recipe[Food] 
class VeggieRecipe(val ingredients: List[Vegetable]) extends Recipe[Vegetable] 
class GreenVeggieRecipe(val ingredients: List[GreenVeggie]) extends Recipe[GreenVeggie] 

`Recipe` is a generic trait that accepts a covariant parameter (indicated by `[+A]`), and accepts a list of parameter type `A`. Three classes that extend `Recipe` were created: `GenericRecipe`, where `Recipe`'s type parameter is `Food`, `VeggieRecipe`, where `Recipe`'s type parameter is `Vegetable`, and`GreenVeggieRecipe`, where `Recipe`'s type parameter is `GreenVeggie`.

// Function that accepts a Recipe with parameter Food, and prints out the ingredients
def printRecipe(recipe: Recipe[Food]): Unit = println(recipe.ingredients.map(_.name))

// Creating instances of the different Recipes
val generalRecipe = new GenericRecipe(List(Food("Chicken"), Food("Apple")))
val veggieRecipe = new VeggieRecipe(List(Vegetable("Carrot"), Vegetable("Lettuce")))
val greenVeggieRecipe = new GreenVeggieRecipe(List(GreenVeggie("Spinach"), GreenVeggie("Kale")))

printRecipe(generalRecipe)     // List(Chicken, Apple)
printRecipe(veggieRecipe)      // List(Carrot, Lettuce)
printRecipe(greenVeggieRecipe) // List(Spinach, Kale)

The function `printRecipe` is defined such that it accepts a `Recipe` object, with its parameter as `Food`. We can see that `printRecipe` accepts a `GenericRecipe`, `VeggieRecipe`, and `GreenVeggieRecipe` as its argument. This is what covariant types allow developers to acheieve. Assigning a direct relationship to generic classes allows for developers to acheieve this type of abstraction.

The following image more closely details this covariance.


This image shows that `Food` is a parent class of `Vegetable`, which is a parent class of `GreenVeggie`. As we can see, by covariance, `Recipe[Food]` is a parent class of `Recipe[Vegetable]`, which is a parent class of `Recipe[GreenVeggie]`

Now, we will consider a slightly different example.

// Creation of abstract class Vehicle
abstract class Vehicle {
  def name: String
}

// Creation of classes Car and Train, both of which extend Vehicle
class Car(val name: String) extends Vehicle
class Train(val name: String) extends Vehicle

// Function that accepts a list of vehicles
def printVehicleNames(vehicles: List[Vehicle]): Unit =
  vehicles.foreach {
    vehicle => println(vehicle.name)
  }

val cars: List[Car] = List(Car("Toyota"), Car("Honda"))
val trains: List[Train] = List(Train("Bombardier"), Train("GE"))

printVehicleNames(cars)       // prints: Toyota, Honda
printVehicleNames(trains)     // prints: Bombardier, GE

Note that in this example, we have that `Car` and `Train` are subclasses of `Vehicle`. The function `printVehicleNames` accepts `List[Vehicle]` as its input. By covariance, this means that `List[Train]` and `List[Car]` are also accepted, as we know that `Train` and `Car` are child classes to `Vehicle`.

However, in this example, we did not indicate anywhere using the notation of `[+T]` as mentioned before. This is because `List`, as well as many other immutable types in Scala's standard library such as `Seq`, and `Vector` are defined to be covariant data types.

### Contravariance
[comment]: # (we should mention that Scala does not support multiple inheritance, so )

Contravariance represents a relationship where the hierarchy of type parameters is reversed when the type parameter is passed into a generic type. This produces the opposite relationship than that of produced by covariance.

If `A` is a *supertype* of `B`, and we have a generic type `G[T]` where `T` is contravariant, then `G[A]` is a *subtype* of `G[B]`. Notice, if `T` was covariant, then `G[A]` would be a *supertype* of `G[B]`.

The following is a concrete example:

abstract class Vehicle(name: String) 
class Car(val name: String) extends Vehicle(name)

This snippet defines an abstract `Vehicle` class with subclass `Car`.

abstract class Mechanic[-VehicleType]:
  def fix(vehicle: VehicleType): Unit

The Mechanic generic class has the type parameter `VehicleType`. Notice the `-` in front of the type parameter. This is the syntax to define `Mechanic` as a contravariant type.

val vehicleMechanic1: Mechanic[Vehicle] = null
val carMechanic1: Mechanic[Car] = vehicleMechanic1  
// Code compiles successfully

This example shows that a vehicle mechanic is also a car mechanic. Since `Vehicle` is a supertype of `Car`, one would expect a vehicle mechanic to also be able to fix a car. Since the parameter type of `Mechanic` is contravariant, `Mechanic[Vehicle]` is a subtype of `Mechanic[Car]`. Thus we can assign `carMechanic1` values of type `Mechanic[Vehicle]`, i.e `vehicleMechanic`.

val carMechanic2: Mechanic[Car] =  null 
val vehicleMechanic2: Mechanic[Vehicle] = carMechanic2
// Code errors out with the following message
// Found:    (Playground.carMechanic2 : Playground.Mechanic[Playground.Car])
// Required: Playground.Mechanic[Playground.Vehicle]

This example shows that a car mechanic cannot be assigned to a vehicle mechanic. A vehicle mechanic is expected to be able to fix all vehicles, however a car mechanic is only known to fix cars. `Mechanic[Car]` is a supertype of `Mechanic[Vehicle]` and a subtype cannot be assigned a variable of its supertype.

The type relations in the example above is shown by this diagram:


### Invariance

Now, consider the following snippet of code.

class Food(val name: String)
class Vegetable(override val name: String) extends Food(name) 
class GreenVeggie(override val name: String) extends Vegetable(name) 

// Definition of a trait.
trait Recipe[A] {
  def ingredients: List[A]
}

// Class definitions that extend Recipe
class GenericRecipe(val ingredients: List[Food]) extends Recipe[Food] 
class VeggieRecipe(val ingredients: List[Vegetable]) extends Recipe[Vegetable] 
class GreenVeggieRecipe(val ingredients: List[GreenVeggie]) extends Recipe[GreenVeggie] 

// Function that accepts a Recipe with parameter Food, and prints out the ingredients
def printRecipe(recipe: Recipe[Food]): Unit = println(recipe.ingredients.map(_.name))

// Creating instances of the different Recipes
val generalRecipe = new GenericRecipe(List(Food("Chicken"), Food("Apple")))
val veggieRecipe = new VeggieRecipe(List(Vegetable("Carrot"), Vegetable("Lettuce")))
val greenVeggieRecipe = new GreenVeggieRecipe(List(GreenVeggie("Spinach"), GreenVeggie("Kale")))

printRecipe(generalRecipe)
printRecipe(veggieRecipe)
printRecipe(greenVeggieRecipe)

Examine this code closely. On first glance, it might appear to be the same segment of code as the first one provided, but that is not quite correct. When defining the trait with generic `A`, it is no longer indicated as `[A+]`. This minor change in the code causes the code to no longer compile, as the function calls `printRecipe(veggieRecipe)` and `printRecipe(greenVeggieRecipe)` are now invalid. The reason for this is that the indicator that `Recipe` is covariant no longer exists, meaning that there is no longer a covariant relationship. Now, `Recipe[GreenVeggie]` is no longer a subclass of `Recipe[Vegetable]`, and `Recipe[GreenVeggie]` and `Recipe[Vegetable]` are no longer subclasses of `Recipe[Food]`, explaining why these function calls are no longer valid.

This example describes an invariant relationship, as a developer cannot assume any relationships for a generic class with a type parameter that is known to have subclasses or superclasses. For a generic class `G[T]`, we know that `T` is invariant, since `T` does not have `+` or `-` as a prefix.

### Use Cases of Varaince Relationships

#### Liskov substitution principle
Variance relationships extend subtype relationships between classes into subtype relations between generic types with the same classes. This additional information allows for Liskov substitution principle to be applicable when dealing with generics.

#### Producers and Consumers
Variance relations might seem unintutive initially, however, there are heuristics that make it clear if a type parameter should be covariant, contravariant or invariant.

In general, if a generic type can be viewed as a "producer" from the perspective of the type parameter, then the type parameter is covariant. For example, a the built-in `List[T]` class's type parameter `T` is covariant, since a list of type `A` can also contain a subtype `B`. Another example can be that of `R`.

In general, if a generic type can be viewed as a "consumer" from the perspective of the type parameter, then the type parameter is covariant. Consider, generic `FoodConsumer[T]`, where `T` represents the type of food the food consumer can eat. If a food consumer can eat salmon, it also eat fishs. Thus given `Fish` and its subtype `Salmon`, `FoodConsumer[Fish]` is a subtype of `FoodConsumer[Salmon]`.

### Conculsion

When dealing with generic classes, it is not a universal trait for a language to have type variances. Scala's optional usage of this feature gives developers a very useful feature to conceptually think about the relationships they are forming in when dealing with Object Oriented Programming and Generics. It also is useful to allow another level of abstraction, resulting in more expressive and concise code.

In general, variance in type relationships can be classified as covariance, contravariance, and invariance. Consider generic class `G` with parameter type `T`, when given classes `A` and `B`. The parameter types are covariant if `B` is a subtype of `A` implies that `G[B]` is a subtype of `G[A]`. The parameter types are contravariant if `B` is a subtype of `A` implies that `G[B]` is a supertype of `G[A]`. The parameter types are invariant if neither of the previous classifications apply.

### Additional Resources
[comment]: # (Should we use MLA Citations for this?)

1. [Scala Documentation](https://docs.scala-lang.org/)
2. [Variance in Scala](https://docs.scala-lang.org/scala3/book/types-variance.html)
3. [Functional Programming in Scala](https://docs.scala-lang.org/overviews/scala-book/functional-programming.html)
4. [Interview with Scala creator Martin Odersky](https://www.lightbend.com/company/news/jaxenter-interview-with-scala-creator-martin-odersky-on-the-current-state-of-scala)