Programmation appliquée en Scala

Variance

Given classes

class Pair[T](val first: T, val second: T)
class Person(val name: String)
class Student(name: String, val major: String) extends Person(name)

and a method

def makeFriends(p: Pair[Person]): Unit = { ... }

which of the following can be passed to makeFriends?

Only a Pair[Person]
A Pair[Person] and a Pair[Student]
A Pair[Person] and a Pair[Any]
Any Pair[...]

Covariance

By default, generic types are invariant. If G is a generic type, there is no relationship between G[S] and G[T], no matter what the relationship between S and T may be.
Use variance annotation to have generic type follow relationships between type parameters.
Covariance: Generic type follows in the same direction
```
class Pair[+T](val first: T, val second: T)
```
Now Pair[Student] <: Pair[Person]
Good choice for immutable collections (e.g. Seq[+A])

Contravariance

A Friend[T] is willing to befriend anyone of type T.

trait Friend[T] {
def befriend(someone: T)
}

Suppose you have a function

def makeFriendWith(s: Student, f: Friend[Student]): Unit = { f.befriend(s) }

What should you be able to pass in for f?

Only a Friend[Student]
A Friend[Person] and a Friend[Student]
A Friend[GraduateStudent] and a Friend[Student]
Any Friend[...]

Contravariance

A generic type G is contravariant if
```
S <: T => G[T] <: G[S]
```

For example,

Student <: Person => Friend[Person] <: Friend[Student]

Indicated with - annotation:

trait Friend[-T] {
  def befriend(someone: T)
}

Producers and Consumers

Can have both variance types in a single generic type:
```
trait Function1[-T, +R]
```

Can you call

def friends(students: Vector[Student], find: Function1[Student, Person])

with

def findStudent(p: Person) : Student

Of course—it is willing to consume any person, so it will surely consume Student objects
And it produces Student objects, which are Person objects
Consumers are contravariant, producers covariant

Mutable Collections

Can you convert an Array[Student] to an Array[Person]?

That would be bad:

val students = Array(student1, student2)
val people = students // Not legal, but suppose it was...
people(0) = new Person("Fred")

Now students(0) is a Person, not a Student!

In Java, this is a run-time error (ArrayStoreException)
In Scala, the conversion is disallowed.
Mutable collections must be invariant.

Co- and Contravariant Positions

How can Scala tell what is a mutable collection?
It doesn't—it only looks at positions

Example:

class Pair[+T](var first: T, var second: T)

Error: “T occurs in contravariant position in first_=(value: T)”
Parameter positions are contravariant, return values covariant

Variance flips inside function parameters:

foldLeft[B](z: B)(op: (A, B) => B): B
               -       +  +     -   +

A can be +, but B must be invariant

Position Workaround

Sometimes, position rules aren't good enough

class Pair[+T](val first: T, val second: T) {
  def replaceFirst(newFirst: T) = new Pair[T](newFirst, second)
}

Rejected because newFirst: T is in contravariant position
Even though nothing dangerous can happen—no mutation

Remedy: Add type parameter to method

def replaceFirst[R >: T](newFirst: R) = new Pair[R](newFirst, second)

R is invariant and can occur in a covariant position

Objects Can't Be Generic

An object can't have a type parameter
There is only one, not one for each type

Need to be careful with empty objects:

abstract class List[+T]
case class ::[T](val head: T, tail: List[T]) extends List[T]
case object Nil extends List[Nothing]

Nothing is a subtype of all types
Therefore, List[Nothing] is a subtype of all List[T]
Consider
```
val lst = new ::(42, Nil)
```
Makes a ::[Int].
Second parameter needs to be a List[Int]
List[Nothing] <: List[Int]

Declaration-Site vs. Use-Site Variance

Java has no “declaration-site” variance of generic types
Java has “use-site” variance: ? extends T, ? super T
PECS: “producer extends, consumer super”

Java collections are mutable, so declaration-site variance is not useful. But use-case variance is:

public class Collections { // This is Java
  public static <T> void copy(List<? super T> dest, List<? extends T> src) { ... }
  ...
}

In Java, it's impossible to declare Comparator as contravariant—must provide variance with every use

public class Collections { // This is Java
  public static <T> void sort(List<T> list, Comparator<? super T>> c) { ... }
  ...
}

You can do use-site variance in Scala too:

def copy[T](dest: Array[_ >: T], src: Array[_ <: T])

Lab

Scary looking lab

You work with a buddy
One of you (the coder) writes the code, the other (the scribe) types up answers
When you get stuck, ask your buddy first!
Switch coder/scribe roles each lab
The coder submits the worksheet. Include the scribe's name in the worksheet!
The scribe submits answers. Include the coder's name in the report!

Part 1: Co- and Contravariant Positions

Look at the count, groupBy, and aggregate methods of the Iterable[+A] trait. Why is it in a covariant position in these methods?
In the “Position Workaround” slide, the replaceFirst method has a type bound. Why can’t you define an equivalent method on a mutable Pair[T]?
```
def replaceFirst[R >: T](newFirst: R) { first = newFirst } // Error
```

It seems unintuitive to disallow the simple version of the replaceFirst method for an immutable Pair[+T]. But there is a reason. Suppose you could define

def replaceFirst(newFirst: T) = new Pair(newFirst, second)

Then you could also define

class NastyDoublePair(x: Double, y: Double) extends Pair[Double](x, y) {
  override def replaceFirst(newFirst: Double)
    = new Pair(math.sqrt(newFirst), second)
}

Now what would happen with this call?

val p: Pair[Any] = new NastyDoublePair(3, 4)
val q = p.replaceFirst("Hello")

Is the first line valid? That is, can you assign a NastyDoublePair to a Pair[Any]?

Is the second line valid? That is, can you call Pair[Any].replaceFirst with a "String" (assuming that it is defined as above?)
What is the problem?
What does Scala do to avoid the problem?

Part 2: Designing With Variance

Let's use the world's simplest map data structure:

class MyMap[K, V](entries: List[(K, V)]) {
  def this() { this(Nil) }
  def get(key: K) = entries.find(_._1 == key) match {
  	case Some(e) => Some(e._2)
  	case None => None
  }
  def put(key: K, value: V) = new MyMap((key, value) :: entries)
}

Make an instance as

val mm = new MyMap[String, Int].put("Fred", 1).put("Wilma", 10).put("Fred", 5)

What do you get for

mm.get("Fred")
mm.get("Barney")

Now let's say we have a function that needs to look up scores for students:
```
def total(students: List[Student], scores: MyMap[Student, Int]) =
  students.map(scores.get(_).getOrElse(0)).sum
```
Should it be ok to pass it a MyMap[Person, Int]?
Adjust the code for MyMap to make that work. What did you do?

Now let's try this the other way around.

def findById(ids: List[Int], people: MyMap[Int, Person]) =
  ids.flatMap(people.get(_))

Should it be ok to pass it a MyMap[Int, Student]?

Make the same adjustment. What happens?
Using the position workaround, fix it so that it works. What did you do?
Why isn't scala.collection.immutable.Map[A, +B] contravariant in A?

Part 3: Order in the Court!

Let's order people by name:

class Person(val name: String) extends Ordered[Person] {
    def compare(that: Person) = name.compareTo(that.name)
}

class Student(name: String, val major: String) extends Person(name)

Make a Person and a Student object. Can you call person.compare(student)? student.compare(person)?

Make a Vector[Person], fill it with some people, and call people.max. What happens.
Repeat with a Vector[Student]. What happens?
Why can't it work? (Hint: Look carefully at the definition of Ordered in Scaladoc.)
Locally define Ordered to be a generic trait with a single abstract method compare(that: T) : Int. Make it contravariant so that a Ordered[Person] is also a Ordered[Student]. Define max[T <: Ordered[T]](s: Seq[T]) = s.reduce(...). What is max?
What happens when you call max(people)? max(students)?
So why isn't Ordered contravariant? It's been discussed at great length here. Just have a glance at it and admire the complexity and the emotions :-)
So, what to do? First off, remove your definition of Ordered, or make T invariant. The call max(students) should no longer compile. In Java, you'd do this:
```
<T extends Comparable<? super T>> max(Collection<T> coll)
```
or in Scala notation
```
def max[T <: Ordered[_ >: T]]
```
Why does this solve the problem?
What happens when you try it?

That's annoying, but there is a workaround. Define

type SuperOrdered[T] = Ordered[_ >: T]
def max[T <: SuperOrdered[T]]

Now what happens?

Homework

Do this as individual work, not with your partner

When all done, email the signed zip files to Fatemeh.Borran@heig-vd.ch