# Programmation appliquée en Scala Copyright © Cay S. Horstmann 2015 # 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`?

1. Only a `Pair[Person]`
2. A `Pair[Person]` and a `Pair[Student]`
3. A `Pair[Person]` and a `Pair[Any]`
4. 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`?

1. Only a `Friend[Student]`
2. A `Friend[Person]` and a `Friend[Student]`
3. A `Friend[GraduateStudent]` and a `Friend[Student]`
4. Any `Friend[...]`

# Contravariance

1. A generic type `G` is contravariant if
`S <: T => G[T] <: G[S]`
2. For example,
`Student <: Person => Friend[Person] <: Friend[Student]`
3. 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 • 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

1. Look at the `count`, `groupBy`, and `aggregate` methods of the `Iterable[+A]` trait. Why is it in a covariant position in these methods?
2. 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`
3. 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]`?
4. Is the second line valid? That is, can you call `Pair[Any].replaceFirst` with a `"String"` (assuming that it is defined as above?)
5. What is the problem?
6. What does Scala do to avoid the problem?

# Part 2: Designing With Variance

1. 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")```
2. 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]`?
3. Adjust the code for `MyMap` to make that work. What did you do?
4. 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]`?
5. Make the same adjustment. What happens?
6. Using the position workaround, fix it so that it works. What did you do?
7. Why isn't `scala.collection.immutable.Map[A, +B]` contravariant in `A`?

# Part 3: Order in the Court!

1. 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)`?
2. Make a `Vector[Person]`, fill it with some people, and call `people.max`. What happens.
3. Repeat with a `Vector[Student]`. What happens?
4. Why can't it work? (Hint: Look carefully at the definition of `Ordered` in Scaladoc.)
5. 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`?
6. What happens when you call `max(people)`? `max(students)`?
7. 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 :-)
8. 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?
9. What happens when you try it?
10. 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