Last updated on Friday, December 13, 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)

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.

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.

Contravariant field

Scala rejects the following definition. Why?

case class C[-A](a: A)

Show error message

case class C[-A](a: A) // Error
                 // ^ contravariant type A occurs in covariant position in type A of value a

Double negation

Scala rejects the following definition. Why?

  trait C[-A]:
    def app(f: A => Int): Int

Show error message

  trait C[-A]:
    def app(f: A => Int): Int // Error
            // ^ contravariant type A occurs in covariant position in type A => Int of parameter f

Free and bound functions

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

src/main/scala/variance/CounterExamples.scala

Why?

Show error message

  trait F[+A]:
    def f(a: A): A // Error
          // ^ covariant type A occurs in contravariant position in type A of parameter a

Extension methods

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 = ???

src/main/scala/variance/CounterExamples.scala

Why?

Show error message

  trait Foldable1[+A]:
    def fold(a: A)(f: (A, A) => A): A // Error
             // ^               ^ covariant type A occurs in contravariant position in type (A, A) => A of parameter f
             // ^ covariant type A occurs in contravariant position in type A of parameter a

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 work 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!

Exercises from the slides

Array Typing Problem

Arrays in Java are covariant, but covariant array typing causes problems. Do you know why?

To see why, let’s explore with an example:

Consider a class IntSet that defines binary trees storing sets of integers. A set of integers is either an empty set represented by an empty tree, or a non-empty set stored in a tree which consists of one integer and two subtrees. In Java, IntSet can be implemented as below:

sealed interface IntSet permits Empty, NonEmpty {}
final class Empty implements IntSet {}
final class NonEmpty implements IntSet {
  private final int elem;
  private final IntSet left, right;
  public NonEmpty (int elem, IntSet left, IntSet right) {
    this.elem = elem;
    this.left = left;
    this.right = right;
  }
}

In Scala, IntSet would be written as follows:

sealed trait IntSet
case class Empty() extends IntSet
case class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet

Now consider the Java code below:

NonEmpty[] a = new NonEmpty[]{
  new NonEmpty(1, new Empty (), new Empty())};
IntSet[] b = a ;
b[0] = new Empty();
NonEmpty s = a[0];

It looks like in the last line, we assigned an Empty value to a variable of type NonEmpty! What went wrong?

The problematic array example would be written as follows in Scala:

val a: Array[NonEmpty] = Array(NonEmpty(1, Empty(), Empty()))
val b: Array[IntSet] = a
b(0) = Empty()
val s: NonEmpty = a(0)

When you try out this example, what do you observe?

A type error in line 1
A type error in line 2
A type error in line 3
A type error in line 4
A program that compiles and throws an exception at run-time
A program that compiles and runs without exception

Liskov Substitution Principle

The Liskov Substitution Principle (LSP) tells us when a type can be a subtype of another:

If A <: B, then everything one can to do with a value of type B one should also be able to do with a value of type A.

Assume the following type hierarchy and two function types:

trait Fruit
class Apple extends Fruit
class Orange extends Fruit
type A = Fruit => Orange
type B = Apple => Fruit

According to the LSP, which of the following should be true?

A <: B
B <: A
A and B are unrelated.

Prepend

Consider adding a prepend method to List which prepends a given element, yielding a new list.

A first implementation of prepend could look like this:
```
trait List[+T]: 
   def prepend(elem: T): List[T] = Node(elem, this)
```
But that does not type-check. Why?
1. prepend turns List into a mutable class.
2. prepend fails variance checking.
3. prepend’s right-hand side contains a type error.
Given the second implementation of prepend:
```
trait List[+T]: 
  def prepend [U >: T] (elem: U): List[U] = Node(elem, this)
```
What is the result type of this function (Apple <: Fruit, Orange <: Fruit):
```
def f(xs: List[Apple], x: Orange) = xs.prepend(x)
```
Possible answers:
1. does not type check
2. List[Apple]
3. List[Orange]
4. List[Fruit]
5. List[Any]