11. Givens and type classes
Start a REPL on the project with scala repl ., import fullybooked.* and java.time.LocalTime, and ask it to sort two things:
scala> tonight.map(_.time).sorted.take(3)
val res0: List[LocalTime] = List(18:00, 18:30, 18:45)
scala> tonight.sorted
-- [E172] Type Error: ------------------------------------------------------------------------------
1 |tonight.sorted
| ^
|No given instance of type Ordering[fullybooked.Booking] was found for parameter ord of method sorted in trait StrictOptimizedSeqOps.
|I found:
|
| scala.math.Ordering.ordered[fullybooked.Booking](
| /* missing */summon[scala.math.Ordering.AsComparable[fullybooked.Booking]])
|
|But no implicit values were found that match type scala.math.Ordering.AsComparable[fullybooked.Booking].
|
|The following import might make progress towards fixing the problem:
|
| import scala.math.Ordered.orderingToOrdered
|
1 error found
The times sort and the bookings don’t. The error says what’s missing: “No given instance of type Ordering[fullybooked.Booking] was found for parameter ord of method sorted”. So sorted has a parameter we’ve never passed, an Ordering[Booking] called ord. The compiler fills in a parameter like that one by looking for a value of the right type.
11.1. A value the compiler can find
An Ordering[A] is Scala’s Comparator<A>, an object that knows how to compare two values of type A. The library has one for LocalTime because LocalTime is Comparable. It has none for Booking and can’t guess whether we’d want bookings in order of time, name or size.
Add a line to the Booking companion in model.scala, above walkIn, to supply one:
given Ordering[Booking] = Ordering.by(booking => booking.time)
The word given declares a value that the compiler is allowed to pass on our behalf. It needs no name, because it’s looked up by type. Ordering.by builds an ordering from a function, here the one that picks out a booking’s time. Restart the REPL and import fullybooked.* again:
scala> tonight.sorted.map(_.party.name).take(3)
val res0: List[String] = List("Haddad", "Nakamura", "Abara")
scala> tonight.min.party.name
val res1: String = "Haddad"
scala> tonight.max.party.name
val res2: String = "Fitzgerald"
scala> tonight.sorted(using Ordering.by(booking => booking.party.size)).map(_.party.size)
val res3: List[Int] = List(2, 2, 2, 3, 4, 5, 6, 7)
All three of sorted, min and max work on bookings now, though none of the calls mentions the ordering. max gives the booking with the latest time. The last line passes a different ordering by hand, after the keyword using, to sort by party size. Any call can override the given that way.
When a method wants an Ordering[Booking], the compiler looks in two places. One is the code around the call: any given declared there or imported into it. Givens need their own form of import, import some.pkg.given, because an import ending in .* leaves them out. The other place is the companion of each type involved, which is why an ordering in the companion of Booking is available everywhere without an import.
11.2. A type class of our own
Fully Booked has collected several methods that turn a value into text for the staff: describe for a status, explain for an error, label for a booking. One method that prints a list of statuses, errors or bookings would have to know which of those names goes with the type it was given. Create display.scala:
package fullybooked
trait Display[A]:
def text(value: A): String
object Display:
given Display[Status]:
def text(status: Status): String = describe(status)
given Display[BookingError]:
def text(error: BookingError): String = explain(error)
given Display[Booking]:
def text(booking: Booking): String = label(booking)
The trait Display[A] has one method, text, which turns an A into a string. The three givens in the companion each implement the trait for one type, using the method we already had. The colon after given Display[Status] opens a body, like the colon after a class header.
To get this in Java we’d have Status implement an interface. Our Status hasn’t been touched and doesn’t know that Display exists, so a Display[LocalTime] for a class we don’t own would be just as easy to write. A trait with a type parameter and a set of given instances, as Display and Ordering both are, is called a type class.
Now a method can ask for any type that has a Display. Add these to display.scala:
def lines[A](items: List[A])(using display: Display[A]): List[String] =
items.map(item => display.text(item))
def report[A: Display](title: String, items: List[A]): String =
(title :: lines(items).map(line => s" $line")).mkString("\n")
The second parameter list of lines starts with using. Callers leave it out and the compiler fills it in with the given for whatever A turns out to be. If there’s no such given, the call doesn’t compile.
In report, [A: Display] is a context bound: it means “any A that has a given Display”, without giving that value a name. report doesn’t need the name, because it only hands the Display on to lines and the compiler does that as well. The mkString at the end joins a list of strings into one, with its argument between them.
11.3. Extension methods
It would be easier to write item.shown than display.text(item). Scala can add a method to a type from the outside. Add this to the end of display.scala:
extension [A](value: A)(using display: Display[A])
def shown: String = display.text(value)
An extension names the value it extends, in parentheses. Its methods are then written as though they were inside that value’s class. The compiler turns value.shown into an ordinary call with value as its argument, the job a static helper method does in Java. This one applies to any type A that has a Display, so booking.shown and status.shown both work.
A Phone has had no methods of its own since it became an opaque type in chapter 8. An extension inside phone.scala can see that a Phone is a String, and so can use take for the first five characters and drop for the rest. Add this to the end of phone.scala:
extension (phone: Phone)
def formatted: String = s"${phone.take(5)} ${phone.drop(5)}"
Add a test to the end of PhoneTests:
test("a number is formatted with its space"):
assertEquals(Phone.parse("07700900141").map(_.formatted), Some("07700 900141"))
The .only we put after a test’s name in chapter 6 is a method that String doesn’t have. That looks like an extension method, but MUnit was written for Scala 2 as well as Scala 3 and uses Scala 2’s mechanism, an implicit conversion. The conversion turns the string into an object of MUnit’s own that does have only. Scala 2 used the one keyword implicit for conversions, for what are now givens and for using parameters, which is why this chapter’s first error message talked about “implicit values”. Appendix A covers reading that older style.
Add a new @main to the end of main.scala that uses the ordering, report and shown. It calls distinct on the statuses to remove the repeats from that list:
@main def nightReport(): Unit =
println(report("Tonight", tonight.sorted))
println(report("Statuses", tonight.map(_.status).distinct))
println(s"First in: ${tonight.min.shown}")
$ scala run . --main-class fullybooked.nightReport
Tonight
18:00 table 5: Haddad, party of 6
18:30 table 2: Nakamura, party of 2
18:45 table 4: Abara, party of 4
19:30 table 5: Okonkwo, party of 5
19:30 table 1: Patel, party of 2
20:00 table 6: Lindqvist, party of 7 (deposit taken)
20:15 table 3: Moreau, party of 3
21:15 table 2: Fitzgerald, party of 2
Statuses
cancelled (rang to cancel)
at the table since 18:25
at the table since 18:50
confirmed
waiting to be confirmed
First in: 18:00 table 5: Haddad, party of 6
11.4. Instances the compiler writes
For some type classes the compiler can write the instance itself, if you ask with derives. Try it in a plain scala repl:
scala> case class Seat(number: Int)
// defined case class Seat
scala> case class Chair(number: Int)
// defined case class Chair
scala> Seat(4) == Chair(4)
val res0: Boolean = false
scala> import scala.language.strictEquality
scala> Seat(4) == Chair(4)
-- [E172] Type Error: ------------------------------------------------------------------------------
1 |Seat(4) == Chair(4)
|^^^^^^^^^^^^^^^^^^^
|Values of types Seat and Chair cannot be compared with == or !=
1 error found
scala> Seat(4) == Seat(4)
-- [E172] Type Error: ------------------------------------------------------------------------------
1 |Seat(4) == Seat(4)
|^^^^^^^^^^^^^^^^^^
|Values of types Seat and Seat cannot be compared with == or !=
1 error found
scala> case class Stool(legs: Int) derives CanEqual
// defined case class Stool
scala> Stool(3) == Stool(3)
val res3: Boolean = true
By default Scala will compare a Seat with a Chair, two classes that have nothing to do with each other, and the answer is just false. A comparison like that is nearly always a mistake. The import switches on a stricter rule, under which two types can only be compared if there’s a CanEqual for them. Under that rule a Seat can’t even be compared with another Seat. A Stool can, because derives CanEqual asks the compiler to write the instance for it. I haven’t turned strict equality on for Fully Booked, because Status, BookingError and Event would then each need derives CanEqual and a Java type such as LocalTime would need a given written for it. Libraries use derives a great deal: chapter 13 uses it for a configuration reader and chapter 19 for JSON.
11.5. Cats
Cats is a library of type classes, with instances for the standard types and extension methods for using them. Most of the libraries in the rest of this book are built on it. It’s the first dependency that isn’t only for tests, so the line to add to project.scala, above the two for tests, says dep:
//> using dep org.typelevel::cats-core:2.13.0
Create summary.scala, which uses the type class Monoid:
package fullybooked
import cats.Monoid
import cats.syntax.all.*
import java.time.LocalTime
case class Summary(bookings: Int, covers: Int, deposits: BigDecimal)
object Summary:
given Monoid[Summary]:
def empty: Summary = Summary(0, 0, BigDecimal(0))
def combine(a: Summary, b: Summary): Summary =
Summary(a.bookings + b.bookings, a.covers + b.covers, a.deposits + b.deposits)
def summarise(bookings: List[Booking], rule: DepositRule): Summary =
bookings
.filter(holdsTable)
.foldMap(booking => Summary(1, booking.party.size, rule(booking.party)))
A Monoid[A] has two things: a way to combine two values of A into one, and an empty value that changes nothing when it’s combined with another. Numbers under addition are a monoid, with 0 as the empty value. Strings, lists and maps have instances as well, and we’ve just given Summary one. foldMap, which import cats.syntax.all.* adds to List, turns each element into a value with a Monoid and combines them all, starting from empty. In chapter 7, depositsDue did that for one number with map and sum. foldMap does it for three figures at once and would do it for anything else we gave a Monoid.
Cats has a method, traverse, for the job that seatAll did with a fold and a for in chapter 9’s fourth exercise. If you kept your own seatAll, delete it, then add this to summary.scala:
def seatAll(bookings: List[Booking], at: LocalTime): Either[BookingError, List[Booking]] =
bookings.traverse(booking => booking.handle(Arrive(at)))
Mapping handle over the list would give a List[Either[BookingError, Booking]], a list of separate results. traverse gives an Either[BookingError, List[Booking]]: every booking seated, or the first error. With a function that returns an Option it gives an Option of a list, which is None if any element gave None.
The match on four results in validate can go as well. In request.scala, add import cats.data.EitherNel and import cats.syntax.all.* to the imports and replace validate:
def validate(request: BookingRequest): EitherNel[BookingError, (Party, LocalTime)] =
(
nameIn(request).toEitherNel,
sizeIn(request).toEitherNel,
timeIn(request).toEitherNel,
phoneIn(request).toEitherNel
).parMapN((name, size, time, phone) => (Party(name, size, phone), time))
The new validate still runs all four checks. parMapN takes the tuple of their results and a function of four arguments. It calls the function if every result is a Right and otherwise joins the errors together. Two BookingErrors can’t be joined into one, but two lists of them can, so toEitherNel puts each check’s error into a NonEmptyList, Cats’s list that can’t be empty. An Either with a NonEmptyList on the left is an EitherNel, the new return type. A list that can’t be empty is the accurate type for the errors of a failed validation, since there’s always at least one. I’ve used parMapN because Cats also has a mapN, which stops at the first error on an Either as a for would.
The project won’t compile until main.scala and one test have caught up with the new return type. In book, in main.scala, the line after validate becomes reserve(store, party, time).toEitherNel, and the loop that prints the errors becomes for error <- errors.toList do println(s" ${error.shown}"). A NonEmptyList has no foreach for the for to use, hence the toList. Add import cats.syntax.all.* under the package line of that file too. In request.test.scala, import cats.data.NonEmptyList and build the expected errors with NonEmptyList.of(...) where the test had List(...). The output for a bad request hasn’t changed:
$ scala run . --main-class fullybooked.book -- Silva two 8pm "ask for Dev"
Sorry, we couldn't make that booking:
'two' isn't a number of people
'8pm' isn't a time, try 19:30
'ask for Dev' isn't a phone number
Finish with a test file, cats.test.scala, and run the tests:
package fullybooked
import cats.syntax.all.*
import java.time.LocalTime
class CatsTests extends munit.FunSuite:
val eight = LocalTime.of(20, 0)
val confirmed = Booking(Party("Moreau", 3), Table(3, 4), eight, Status.Confirmed)
test("maps of covers combine hour by hour"):
val friday = Map(18 -> 6, 19 -> 5)
val saturday = Map(19 -> 4, 20 -> 10)
assertEquals(friday |+| saturday, Map(18 -> 6, 19 -> 9, 20 -> 10))
test("a summary of tonight"):
assertEquals(summarise(tonight, weekend), Summary(6, 23, BigDecimal(240)))
assertEquals(summarise(List(), weekend), Summary(0, 0, BigDecimal(0)))
test("seatAll seats everyone or reports the first booking that can't be"):
val cancelled = confirmed.copy(status = Status.Cancelled("flu"))
assertEquals(seatAll(List(confirmed, confirmed), eight).map(_.size), Right(2))
assert(seatAll(List(confirmed, cancelled, confirmed), eight).isLeft)
The operator |+| is another way to write combine. On two maps it combines the values that share a key, so seven o’clock’s covers are added and the other hours are kept as they were.
11.6. Functor, monad and other names
Cats and its documentation use names from mathematics for things you’ve already been using. A type with a map, such as List, Option, Either or our own Noted, is a functor. A type that also has flatMap, along with some way of wrapping a plain value such as Some(x) or Right(x), is a monad. The type class that let parMapN join the error lists is called Semigroup, which is a Monoid without the empty.
Each of those is a type class in Cats, with a few laws that an instance is supposed to obey. One of the laws for a functor says that mapping with a function that returns its argument unchanged gives back an equal value. I’ve never needed the mathematics to use the type classes. When a library’s documentation says a type “is a monad”, I read it as “has flatMap, so it works in a for” and carry on.
11.7. Exercises
Solutions are in the book’s downloadable code, under ch11/exercises.
-
Write a given
Ordering[Table]that puts the largest tables first and breaks ties by table number.Ordering.byaccepts a function that returns a tuple, and a negative number of seats sorts the large ones first. -
LocalTimeis Java’s, but it can still be extended. Write an extension methodisWithin(from: LocalTime, to: LocalTime): Booleanon it, and test it againstopensandlastOrders. -
Write a
Display[Table]. Then write one for a list of anything displayable, which startsgiven [A] => (display: Display[A]) => Display[List[A]]:and joins the items with commas. -
Write a case class
Largest(size: Int)with aMonoidwhosecombinekeeps the bigger of two, and usefoldMapto find tonight’s largest party. What shouldemptybe? -
Write
parseAll(numbers: List[String]): Either[BookingError, List[Phone]]withtraverse, givingBadPhonefor the first text that isn’t a number.