Last updated on Monday, October 14, 2024

Variance

This exercise set is intended to help you hone your understanding of covariance and contravariance.

As usual, ⭐️ indicates the most important exercises and questions; 🔥, the most challenging ones; and 🔜, the ones that are useful to prepare for future lectures.

You do not need to complete all exercises to succeed in this class, and you do not need to do all exercises in the order they are written.

Do these exercises on paper first. Using the compiler is a great way to confirm your understanding, but starting from the code will not help you develop your intuition and understanding of these rules, since the compiler will do all the work for you. After completing a first draft on paper, you can either check our solution, or check your solutions on your computer. To do the latter, you can download the scaffold code (ZIP).

Subtyping of variant types ⭐️

Recall that:

Lists are covariant in their only type parameter.
Functions are contravariant in the argument, and covariant in the result.

Consider the following hierarchies:

abstract class Fruit
class Banana extends Fruit
class Apple extends Fruit
abstract class Liquid
class Juice extends Liquid

Consider also the following typing relationships for A, B, C, D: A <: B and C <: D.

Fill in the subtyping relation between the types below. Bear in mind that it might be that neither type is a subtype of the other.

Left hand side	?:	Right hand side
List[Banana]		List[Fruit]
List[A]		List[B]
Banana => Juice		Fruit => Juice
Banana => Juice		Banana => Liquid
A => C		B => D
List[Banana => Liquid]		List[Fruit => Juice]
List[A => D]		List[B => C]
(Fruit => Juice) => Liquid		(Banana => Liquid) => Liquid
(B => C) => D		(A => D) => D
Fruit => (Juice => Liquid)		Banana => (Liquid => Liquid)
B => (C => D)		A => (D => D)

Understanding variance ⭐️

Variance rules are designed to keep type casts safe: any time the compiler rejects code for variance reasons, it does so to avoid runtime errors that could happen if these protections were not in place.

Here are some examples. For each, think of what might go wrong if the compiler didn’t disallow this pattern:

Scala rejects the following definition. Why?
```
case class C[-A](a: A)
```
Scala rejects the following definition. Why?
```
trait C[-A]:
  def foo(f: A => Int): Int
```
Scala rejects the following definition:
```
trait F[+A]:
  def f(a: A): A
```
… yet it accepts the following:
```
def f[A](a: A): A = a
```
Why?

Scala rejects the following definition:

trait Foldable1[+A]:
  def fold(a: A)(f: (A, A) => A): A

… yet it accepts the following:

trait Foldable2[+A]
extension [A](t: Foldable2[A])
  def fold(a: A)(f: (A, A) => A): A

Why?

Testing subtyping relationships

Scala’s compiler automatically checks variance rules. Can we make it shows us what it inferred? Write a function assertSubtype so that assertSubtype[Int, String] causes a compilation error, but assertSubtype[String, Object] compiles.

Implementing classes with variance

Here is a simple trait for stacks:

trait Stack[T]:
  /** Peek at the top of this stack */
  def peek(): Option[T]

  /** Create a new stack with one more entry, at the top */
  def push(t: T): Stack[T]
  /** Separate the top entry from the rest of the stack */
  def pop(): (Option[T], Stack[T])

src/main/scala/variance/Variance.scala

Write an implementation of this trait.
Write a function that takes a list of stacks and collects the top of each stack into a new stack.
```
def joinStacks[T](l: List[Stack[T]]): Stack[T] =
  ???
```
src/main/scala/variance/Variance.scala
🔜 An operation similar to this one is often called “join” in parallel programming. We will encounter it in the parallelism week, and we’ll study a structure similar to the Box below when we study Futures.
What happens if you try to call join with a mix of stacks with different element types (different Ts)? Can you even put two such stacks together in a list? Why or why not?
```
def mkStackInt(): Stack[Int] =
  ???

def mkStackString(): Stack[String] =
  ???

// Does this work?
// val tops = joinStacks(List(mkStackInt(), mkStackString()))
```
src/main/scala/variance/Variance.scala
Assume that we want to change Stack[T] to allow for multiple stacks with different T types to be placed together in a list. Is there a variance annotation for T that will allow this? Which one makes more sense?

Try to perform the change by adding an annotation on T in Stack[T]. What problem do you run into? Why is this error reasonable? (What would go wrong otherwise?) Change the signature of push to make it work.
Is it always possible to turn an invariant trait into a covariant one? Consider the following example:
```
trait Drawer[T]:
  def get(): T
  def put(t: T): Drawer[T]

case class IncrementingDrawer(i: Int) extends Drawer[Int]:
  def get() = i - 1
  def put(j: Int) = IncrementingDrawer(j + 1)
```
src/main/scala/variance/Variance.scala
Can you make Drawer covariant in T without breaking IncrementingDrawer?
From question 5, it is clear that covariance puts restrictions on what classes that implement a covariant trait can do (the same is true of contravariance). Based on this, can you think of a good reason to not make a container class (like a List or a Stack) covariant?
Here is another trait, similar to stacks, but storing at most one element. First give T an adequate variance annotation as in the Stack case (this will require other changes, of course), then implement the trait.

trait Box[T]:
  /** Peek at the value inside the box */
  def unbox(): Option[T]

  /** Create a new box with the contents */
  def replace(t: T): Box[T]
  /** Create a new box by applying `f` to the contents of this one */
  def map[T2](f: T => T2): Box[T2]

src/main/scala/variance/Variance.scala

Both of these traits have a way to inspect one element of the container. Change both of them to extend the following HasTop trait, which captures this property.
```
trait HasTop[+T]:
  /** Peek at one value inside this container */
  def top: Option[T]
```
src/main/scala/variance/Variance.scala
Drawer[T] is required to be invariant to be compatible with IncrementingDrawer, but HasTop[+T] is covariant in T. Can Drawer[T] implement HasTop[T] without breaking IncrementingDrawer?
Rewrite the join operation to work on lists of HasTop instances, rather than stacks. Does this join still works if you remove the covariance annotation on T in Box and Stack? Why?

def joinTops[T](l: List[HasTop[T]]): List[T] =
  ???

src/main/scala/variance/Variance.scala

A variance puzzle 🔥

This exercise goes beyond what will be on the exam. It’s hard to get an intuition for it: instead, if you want to complete it, you may find our complete writeup on variance rules useful.

Assume the following two classes or traits…

C[-A, +B]
F[ A, +B] extends C[A, B]

… and the following subtyping relationships…

A <: B
X <: Y

… what are the relations between the following pairs?

C[A, Y] and F[B, X];
F[A, X] and C[A, Y]?

Check in a worksheet it you’re not sure that your answer is correct!