10. Generics and variance

When the restaurant is full the staff take a name and put the party on a waiting list. A waiting-list entry has a party and a time, as a booking does. The staff ask the same thing of both: who’s first? To write that question once, so that it works for bookings and for the waiting list, we need type parameters, which Java calls generics. Scala writes them in square brackets. It also has its own answer to whether a list of bookings can be used as a list of something more general.

10.1. One method for two types

Give the two types something in common. In model.scala, add a trait and a case class above Booking:

trait Timed:
  def time: LocalTime

case class WaitlistEntry(party: Party, time: LocalTime) extends Timed

Then make Booking extend the trait, by changing the line that closes its parameter list:

case class Booking(
    party: Party,
    table: Table,
    time: LocalTime,
    status: Status = Status.Requested
) extends Timed:

A field is allowed to stand in for a method that a trait declares. Each class already has a field called time, so neither needs anything added.

Create waitlist.scala with a first attempt at the question:

package fullybooked

import java.time.LocalTime

def earliestOf(items: List[Timed]): Option[Timed] =
  items.minByOption(_.time)

A call such as earliestOf(tonight) compiles and finds the Haddad booking, but its type is Option[Timed]. The compiler no longer knows there’s a booking inside, so earliestOf(tonight).map(_.party) is an error: a Timed has no party.

10.2. Type parameters and bounds

Add a second version to waitlist.scala:

def earliest[A <: Timed](items: List[A]): Option[A] =
  items.minByOption(_.time)

The A in square brackets is a type parameter. Java would write this method as <A extends Timed> Optional<A> earliest(List<A> items). Scala puts type parameters after the method’s name and spells extends as <:. Here A <: Timed gives A an upper bound: it can be Timed or any subtype of Timed. The method needs the bound because it uses time. Without one, A could be any type at all and the body wouldn’t compile.

Hand earliest a list of bookings and A is Booking, so an Option[Booking] comes back where earliestOf gave an Option[Timed]. The caller doesn’t have to say what A is, because the compiler infers it from the argument.

Create generics.test.scala:

package fullybooked

import java.time.LocalTime

class GenericsTests extends munit.FunSuite:
  val seven = Booking(Party("Okonkwo", 5), Table(5, 6), LocalTime.of(19, 30))
  val eight = Booking(Party("Lindqvist", 7), Table(6, 8), LocalTime.of(20, 0))
  val waiting = WaitlistEntry(Party("Silva", 2), LocalTime.of(19, 0))

  test("earliest keeps the type it was given"):
    assertEquals(earliest(List(eight, seven)).map(_.party.name), Some("Okonkwo"))
    assertEquals(earliest(List(waiting)).map(_.party.size), Some(2))

  test("a list of bookings is a list of timed things"):
    val bookings: List[Booking] = List(eight, seven)
    assertEquals(earliestOf(bookings).map(_.time), Some(LocalTime.of(19, 30)))
    assertEquals(earliestOf(List(eight, waiting)), Some(waiting))

Run the tests. The first reaches a party through the result of earliest, where earliestOf(tonight).map(_.party) was an error.

As in Java, the compiler erases type arguments, so a List[Booking] and a List[Table] are the same class once the program is running.

10.3. Is a list of bookings a list of timed things?

The second test passes bookings, a List[Booking], to earliestOf, whose signature asks for a List[Timed], and the compiler accepts it. In Java it wouldn’t, because a List<Booking> isn’t a List<Timed>. A Java method that wants to accept either has to ask for a List<? extends Timed>.

Scala lets the author of a class settle this once, where Java leaves it to every method that uses the class. The library declares its list as List[+A]. The plus sign means that a list of some type is also a list of each of that type’s supertypes, so a List[Booking] is a List[Timed]. A type parameter marked with a plus is covariant.

The plus is safe on List because a list can’t be changed. All anyone can do with a List[Timed] is take timed things out, and bookings are timed things. It wouldn’t be safe for a collection you can add to. Put import scala.collection.mutable.ArrayBuffer under the other import in waitlist.scala and add a method that takes a buffer, with a @main to call it:

def addLatecomer(arrivals: ArrayBuffer[Timed], time: LocalTime): Unit =
  arrivals += WaitlistEntry(Party("Latecomer", 2), time)

@main def latecomers(): Unit =
  val arrivals = ArrayBuffer(tonight(3), tonight(4))
  addLatecomer(arrivals, LocalTime.of(19, 45))
  println(arrivals.map(_.time))
$ scala compile .
[error] ./waitlist.scala:17:16
[error] Found:    (arrivals : scala.collection.mutable.ArrayBuffer[fullybooked.Booking])
[error] Required: scala.collection.mutable.ArrayBuffer[fullybooked.Timed]
[error]   addLatecomer(arrivals, LocalTime.of(19, 45))
[error]                ^^^^^^^^
Compilation failed

The compiler inferred ArrayBuffer[Booking] for arrivals from its two elements. If the call were allowed, addLatecomer would add a WaitlistEntry to it. The next line of code that took an element out expecting a Booking would then get something else. Java’s arrays do allow this kind of substitution and throw an ArrayStoreException at run time when it goes wrong. ArrayBuffer is declared with no sign on its type parameter, which makes it invariant: an ArrayBuffer[Booking] can’t be used as a buffer of anything else.

The fix is to say from the start that the buffer holds timed things, by giving the type argument in square brackets. Change the line that builds the buffer:

@main def latecomers(): Unit =
  val arrivals = ArrayBuffer[Timed](tonight(3), tonight(4))
  addLatecomer(arrivals, LocalTime.of(19, 45))
  println(arrivals.map(_.time))
$ scala run . --main-class fullybooked.latecomers
ArrayBuffer(19:30, 19:30, 19:45)

10.4. Functions go the other way

Add two more methods to the end of waitlist.scala, each of which takes a function for turning an item into text:

def timesOf(items: List[Timed], show: Timed => String): List[String] =
  items.map(show)

def bookingLines(bookings: List[Booking], show: Booking => String): List[String] =
  bookings.map(show)

Add a test to the end of GenericsTests:

  test("a function of any timed thing will do for bookings"):
    val clock: Timed => String = item => s"at ${item.time}"
    assertEquals(bookingLines(List(seven), clock), List("at 19:30"))

The test gives bookingLines a Timed => String where it asks for a Booking => String. That compiles, and it should: a function that can describe any timed thing can certainly describe a booking. timesOf couldn’t take a Booking => String, because it might hand that function a waiting-list entry.

So a function that takes something more general can be used in place of one that takes something more specific, the reverse of the rule for lists. The library declares one-argument functions as Function1[-T1, +R], with a minus on what goes in and a plus on what comes out. A type parameter marked with a minus is contravariant. The signature of map on a Java stream writes the same rule out at the point of use: Function<? super T, ? extends R>. A plus is allowed on a type parameter whose values only come out and a minus on one whose values only go in. A parameter used both ways gets neither.

I’d expect you to write very few of these signs and to read a great many. They’re all over the documentation of Scala libraries, and being able to read [-T1, +R] as “takes a T1, gives back an R” is most of what’s needed.

10.5. A type parameter of our own

The owner wants to see how each deposit was worked out as well as the figure. That calls for a value which carries notes along with it, whatever type the value happens to be. Create noted.scala:

package fullybooked

case class Noted[+A](value: A, notes: List[String]):
  def map[B](change: A => B): Noted[B] =
    Noted(change(value), notes)

  def flatMap[B](next: A => Noted[B]): Noted[B] =
    val result = next(value)
    Noted(result.value, notes ++ result.notes)

A class can take a type parameter as a method can. The plus on this one makes Noted covariant, which is safe because its value can only be read. Both methods change the value into some other type B. With map the notes stay as they are. The step passed to flatMap returns notes of its own, which go after the ones we already have.

Working out a deposit goes through three methods here, each returning an amount with any note it has to add. Add them to noted.scala with a fourth that chains them:

def charge(party: Party, name: String, rule: DepositRule): Noted[BigDecimal] =
  Noted(rule(party), List(s"$name rule for ${party.size} people: ${rule(party)}"))

def limit(amount: BigDecimal, most: BigDecimal): Noted[BigDecimal] =
  if amount > most then Noted(most, List(s"limited to $most")) else Noted(amount, List())

def regular(amount: BigDecimal, party: Party): Noted[BigDecimal] =
  if party.name == "Okonkwo" then Noted(amount / 2, List("half price for a regular"))
  else Noted(amount, List())

def quoteLonghand(party: Party): Noted[BigDecimal] =
  charge(party, "weekend", weekend).flatMap: full =>
    limit(full, BigDecimal(100)).flatMap: capped =>
      regular(capped, party).map: owed =>
        owed

The chain in quoteLonghand works, but each step is nested inside the one before and the last line just hands back owed. In a for, the three steps would sit one under another.

10.6. What for turns into

Chapter 4 said the compiler turns a for into calls to the collection methods. Start a REPL on the project, import fullybooked.* and compare:

scala> for booking <- tonight if booking.party.size > 4 yield booking.party.name
val res0: List[String] = List("Haddad", "Okonkwo", "Lindqvist")

scala> tonight.withFilter(booking => booking.party.size > 4).map(booking => booking.party.name)
val res1: List[String] = List("Haddad", "Okonkwo", "Lindqvist")

scala> for table <- Table.all.take(2); hour <- List(18, 19) yield (table.number, hour)
val res2: List[(Int, Int)] = List((1, 18), (1, 19), (2, 18), (2, 19))

scala> Table.all.take(2).flatMap(table => List(18, 19).map(hour => (table.number, hour)))
val res3: List[(Int, Int)] = List((1, 18), (1, 19), (2, 18), (2, 19))

Each pair gives the same answer because the second line of the pair is what the compiler makes of the first. In the first pair the only <- became a map and the if became a call to withFilter in front of it. That method does what filter does without building a list in between. The second pair has two <- clauses. The last is a map again and each one before it is a flatMap wrapped around what follows, nested as quoteLonghand is. A for that ends in do has no yield and becomes a call to foreach, which runs a function on each element for its side effects.

The translation goes by method names alone and doesn’t care whether the thing on the right of the <- is a collection. That’s why for worked on Option in chapter 5 and on Either in chapter 9. Noted has a map and a flatMap, so a for will work on it too. Add this to noted.scala:

def quoteFor(party: Party): Noted[BigDecimal] =
  for
    full <- charge(party, "weekend", weekend)
    capped <- limit(full, BigDecimal(100))
    owed <- regular(capped, party)
  yield owed

Add a @main to the end of main.scala:

@main def quote(name: String, size: Int): Unit =
  val result = quoteFor(Party(name, size))
  println(s"Deposit for $name: ${result.value}")
  for note <- result.notes do println(s"  $note")
$ scala run . --main-class fullybooked.quote -- Okonkwo 8
Deposit for Okonkwo: 50
  weekend rule for 8 people: 120
  limited to 100
  half price for a regular

None of the three steps in quoteFor mentions the notes, which flatMap collected along the way. Add a test to the end of GenericsTests to confirm that the two versions agree:

  test("a quote carries its notes"):
    val quote = quoteFor(Party("Okonkwo", 8))
    assertEquals(quote.value, BigDecimal(50))
    assertEquals(quote.notes.size, 3)
    assertEquals(quoteLonghand(Party("Okonkwo", 8)), quote)

10.7. A bound in the other direction

A replace method on Noted would swap the value for a new one and keep the notes. Written as def replace(other: A): Noted[A], it’s rejected by the compiler with “covariant type A occurs in contravariant position”. The plus sign promised that values of type A only come out, and here one goes in. If that were allowed, a Noted[Booking] being passed around as a Noted[Timed] could be handed a waiting-list entry, although its replace only promised to take bookings. The compiler goes by the signature and rejects it whatever the body would do.

Add this version inside Noted instead:

  def replace[B >: A](other: B): Noted[B] =
    Noted(other, notes)

The B >: A here is a lower bound: B is A or something above it. Replacing a booking with a waiting-list entry is fine as long as the result is no longer called a Noted[Booking]. The compiler picks B for itself: a val holding the result has the type Noted[Timed]. Add one last test to the end of GenericsTests:

  test("a noted booking is a noted timed thing"):
    val noted: Noted[Booking] = Noted(seven, List("moved from table 3"))
    val general: Noted[Timed] = noted
    assertEquals(general.notes, noted.notes)
    assertEquals(noted.replace(waiting).value.time, LocalTime.of(19, 0))

In the library, getOrElse on Option[A] is declared with a lower bound: getOrElse[B >: A](default: => B): B. That’s why lookUp went on compiling in chapter 8. Asked for the value of an Option[Phone] or else a String, the compiler chose a B above both, the union type Phone | String.

10.8. Exercises

Solutions are in the book’s downloadable code, under ch10/exercises.

  1. Write latest, the counterpart of earliest, and use it to find the name of tonight’s last party.

  2. Write pairs[A, B](first: List[A], second: List[B]): List[(A, B)], which gives every combination of one element from each list. It has two type parameters and no bounds.

  3. Rewrite validateFast from chapter 9 without for, as the compiler would.

  4. Write plain[A](value: A): Noted[A], which starts a value off with no notes, and withNote[A](noted: Noted[A], note: String): Noted[A], which adds one. Use flatMap for the second.

  5. Take the + out of Noted[+A] and compile the tests. Which line fails, and why does replace still compile?

  6. Decide which of these compile, then try them: val a: Option[Timed] = Some(tonight.head), val b: Booking => Timed = (item: Timed) => item and val c: Timed => Booking = (booking: Booking) => booking.