4. Collections
Over an evening the staff need answers from the bookings, such as how many people are coming and whether anything is free at eight. Each of those is a question about a list. In Scala you answer it with methods on the list itself, where Java would use a loop or a stream. I said in chapter 1 that this is where the differences from Java start to matter, so most of this chapter is spent at the REPL, trying those methods on real bookings.
4.1. An evening’s bookings
Add a file called tonight.scala to the project:
package fullybooked
import java.time.LocalTime
val tonight = List(
Booking(Party("Haddad", 6), Table(5, 6), LocalTime.of(18, 0), Status.Cancelled),
Booking(Party("Nakamura", 2), Table(2, 2), LocalTime.of(18, 30), Status.Seated),
Booking(Party("Abara", 4), Table(4, 4), LocalTime.of(18, 45), Status.Seated),
Booking(Party("Okonkwo", 5), Table(5, 6), LocalTime.of(19, 30), Status.Confirmed),
Booking(Party("Patel", 2), Table(1, 2), LocalTime.of(19, 30)),
Booking(Party("Lindqvist", 7), Table(6, 8), LocalTime.of(20, 0), Status.Confirmed),
Booking(Party("Moreau", 3), Table(3, 4), LocalTime.of(20, 15), Status.Confirmed),
Booking(Party("Fitzgerald", 2), Table(2, 2), LocalTime.of(21, 15), Status.Confirmed)
)
We’ll also need the restaurant’s tables. Put them in a companion for Table, in model.scala. If you did exercise 4 in chapter 3, you’ll have this already:
object Table:
val all = List(
Table(1, 2), Table(2, 2), Table(3, 4),
Table(4, 4), Table(5, 6), Table(6, 8)
)
Start the REPL on the whole project by running scala repl . and import two things before anything else, the project’s package and LocalTime:
scala> import fullybooked.*
scala> import java.time.LocalTime
scala> tonight.size
val res0: Int = 8
scala> tonight.map(booking => booking.party.name)
val res1: List[String] = List(
"Haddad",
"Nakamura",
"Abara",
"Okonkwo",
"Patel",
"Lindqvist",
"Moreau",
"Fitzgerald"
)
scala> tonight.filter(booking => booking.party.size >= 6).map(booking => booking.party.name)
val res2: List[String] = List("Haddad", "Lindqvist")
map calls the lambda on every element and returns a list of the results, so a list of bookings becomes a list of names. Chaining it after filter, which we used in chapter 1, reads left to right: keep the big parties, then take their names. The Java for that last line would be tonight.stream().filter(...).map(...).toList(), with the same two lambdas in the middle.
I’ll leave the two imports out of the sessions that follow. My sessions each number their results from res0, while yours will carry on counting.
4.2. Shorter lambdas
A lambda like booking => booking.party.name gives its argument a name only to use it once. For that case Scala has a shorthand, _.party.name, in which the underscore stands for the argument:
scala> tonight.map(_.party.size).sum
val res0: Int = 31
scala> tonight.count(holdsTable)
val res1: Int = 6
scala> tonight.sortBy(_.party.size).map(_.party.name).take(3)
val res2: List[String] = List("Nakamura", "Patel", "Fitzgerald")
scala> tonight.maxBy(_.party.size).party.name
val res3: String = "Lindqvist"
scala> tonight.exists(_.status == Status.Cancelled)
val res4: Boolean = true
scala> tonight.forall(_.party.size <= Booking.largestParty)
val res5: Boolean = true
Tonight’s eight bookings add up to 31 people, the cancelled party included. Six of the eight currently hold a table. A method’s name can go wherever a lambda is expected. That’s how count was handed holdsTable directly. The rest will look familiar if you’ve used Java streams: sortBy orders the list by whatever the lambda returns, take(3) keeps the first three, and exists and forall are anyMatch and allMatch under other names.
The underscore only works when the argument is used once. I use it for short things like _.party.size and go back to a named argument as soon as the lambda does any real work.
sortBy also works with Java types that implement Comparable, such as LocalTime. Change frontDesk in main.scala so that it prints tonight’s bookings in order of arrival, and run it from a second terminal so that the REPL stays open:
@main def frontDesk(): Unit =
for booking <- tonight.sortBy(_.time) do
println(s"${label(booking)}, ${describe(booking.status)}")
$ scala run . --main-class fullybooked.frontDesk
18:00 table 5: Haddad, party of 6, cancelled
18:30 table 2: Nakamura, party of 2, at the table
18:45 table 4: Abara, party of 4, at the table
19:30 table 5: Okonkwo, party of 5, confirmed
19:30 table 1: Patel, party of 2, waiting to be confirmed
20:00 table 6: Lindqvist, party of 7 (deposit taken), confirmed
20:15 table 3: Moreau, party of 3, confirmed
21:15 table 2: Fitzgerald, party of 2, confirmed
The --main-class option is there because this chapter adds a second @main to the project later on. With more than one, the scala command has to be told which to run, by its full name including the package.
4.3. When there might be no answer
Look for a booking by the party’s name:
scala> tonight.find(_.party.name == "Patel")
val res0: Option[Booking] = Some(
Booking(
party = Party(name = "Patel", size = 2),
table = Table(number = 1, seats = 2),
time = 19:30,
status = Requested
)
)
scala> tonight.find(_.party.name == "Smith")
val res1: Option[Booking] = None
The Patel booking comes back wrapped in Some. The search for Smith finds no booking and returns None. Both results have the type Option[Booking]. A Scala method uses Option in its return type to say that there might be no answer. It’s also the fix for the loose end in chapter 1, where minBy had to be protected by an isEmpty check that was easy to leave out. Chapter 5 is about Option. Until then, be aware that minBy and maxBy assume there’s an answer and throw an exception when there isn’t.
4.4. Grouping and maps
How many people is the kitchen cooking for in each hour?
scala> val covers = tonight.filter(holdsTable).groupBy(_.time.getHour).map((hour, bookings) => (hour, bookings.map(_.party.size).sum))
val covers: Map[Int, Int] = Map(20 -> 10, 21 -> 2, 18 -> 6, 19 -> 5)
scala> covers(19)
val res0: Int = 5
scala> covers.getOrElse(22, 0)
val res1: Int = 0
scala> covers.toList.sorted
val res2: List[(Int, Int)] = List((18, 6), (19, 5), (20, 10), (21, 2))
Read the long line from the left. Once filter has dropped the two bookings that don’t hold a table, groupBy puts the rest into groups by whatever its lambda returns, which here is the hour of arrival, and hands back a Map from each hour to the list of bookings in it. A list per hour is more than we asked for. The final map goes through the entries of that Map, each of them a key with its value. A lambda with two arguments, such as (hour, bookings) => ..., receives the two separately. Ours gives back the hour with a head count, making the final result a Map from hours to people.
The REPL prints each entry as 20 -> 10. The arrow is also how you write an entry yourself, as in Map(18 -> 6, 19 -> 5). 18 -> 6 is another way of writing the tuple (18, 6).
Notice the order the entries came back in: 20, 21, 18, 19. A Map doesn’t keep any order. To print one sensibly, turn it into a list of pairs and sort that, as the last line does. A lookup is written like a method call, covers(19). A plain lookup of a missing key throws an exception, so if the key might not be there, use getOrElse and say what you want back.
4.5. Which tables are free
scala> val taken = tonight.filter(holdsTable).map(_.table.number).toSet
val taken: Set[Int] = Set(5, 6, 2, 3, 4)
scala> taken.contains(1)
val res0: Boolean = false
scala> Table.all.map(_.number).filterNot(taken.contains)
val res1: List[Int] = List(1)
Two of the bookings that hold a table tonight are for table 2, but a Set holds a value only once, so 2 appears once in taken. Like a Map, a Set has no order. What a Set is good at is answering contains quickly, however big it gets. Handing taken.contains to filterNot leaves the tables that aren’t in the set. Tonight that’s only table 1.
That answer ignores the time, though. A table is really taken at a given moment only if a booking that holds it has started and hasn’t finished. Add a new file, availability.scala:
package fullybooked
import java.time.LocalTime
def freeAt(time: LocalTime, bookings: List[Booking]): List[Table] =
val taken = bookings
.filter(holdsTable)
.filter(booking => !time.isBefore(booking.time) && time.isBefore(booking.leaveBy))
.map(_.table)
.toSet
Table.all.filterNot(taken.contains)
The second filter keeps a booking if time isn’t before its start and is before the leaveBy we gave Booking in chapter 3. Restart the REPL, repeat the two imports, and ask about two different times:
scala> freeAt(LocalTime.of(20, 0), tonight).map(_.number)
val res0: List[Int] = List(1, 2, 3)
scala> freeAt(LocalTime.of(18, 45), tonight).map(_.number)
val res1: List[Int] = List(1, 3, 5, 6)
freeAt is still a simplification, because it only asks about one moment. Table 3 is offered at eight although the Moreaus have it from quarter past. Exercise 7 fixes that.
4.6. Flattening and folding
Two more methods are worth knowing, for the cases the others don’t cover. The first is for a lambda that returns a list of its own. Here the lambda gives the arrival and leaving times of a booking, and we apply it to the first three. The session’s last line is the second method, foldLeft:
scala> tonight.take(3).map(booking => List(booking.time, booking.leaveBy))
val res0: List[List[LocalTime]] = List(List(18:00, 20:00), List(18:30, 20:00), List(18:45, 20:15))
scala> tonight.take(3).flatMap(booking => List(booking.time, booking.leaveBy))
val res1: List[LocalTime] = List(18:00, 20:00, 18:30, 20:00, 18:45, 20:15)
scala> tonight.foldLeft(0)((total, booking) => total + booking.party.size)
val res2: Int = 31
map produces a list of lists, one inner list for each booking. flatMap does the same work and then joins the inner lists end to end, leaving a single list of times. Use it whenever each element turns into several.
foldLeft is for a calculation that no existing method does. It takes its arguments in two separate pairs of parentheses, a peculiarity that chapter 7 explains. The first pair holds a starting value. The second holds a lambda with two arguments, the result so far and the next element. foldLeft calls it for each element in turn, carrying the result along. The foldLeft above starts at 0 and adds each party’s size, arriving at the same 31 that map and sum gave earlier. Before writing a fold, check that the method you want doesn’t already exist: sum, count and maxBy could all be written as folds.
4.7. for with yield
The for loops so far have ended in do and run their body for what it does (its “side effects”), such as printing. Ending one in yield makes it build a collection:
scala> for booking <- tonight if booking.party.size >= 6 yield booking.party.name
val res0: List[String] = List("Haddad", "Lindqvist")
scala> for table <- Table.all.take(2); hour <- List(18, 20) yield (table.number, hour)
val res1: List[(Int, Int)] = List((1, 18), (1, 20), (2, 18), (2, 20))
The first has an if after its <- clause, which makes it filter followed by map, written another way. The second has two <- clauses separated by a semicolon and produces every combination of a table and an hour, like a nested loop. Chapter 10 explains how the compiler turns both into calls to the collection methods. I use method chains when there’s one collection involved and for when several are being combined, because that’s where a chain of nested lambdas gets hard to read.
4.8. Lists that don’t change
No method so far has changed the collection it was called on. Adding an element doesn’t change it either:
scala> val seats = Table.all.map(_.seats)
val seats: List[Int] = List(2, 2, 4, 4, 6, 8)
scala> val more = 10 :: seats
val more: List[Int] = List(10, 2, 2, 4, 4, 6, 8)
scala> seats
val res0: List[Int] = List(2, 2, 4, 4, 6, 8)
scala> more.tail eq seats
val res1: Boolean = true
scala> seats :+ 10
val res2: List[Int] = List(2, 2, 4, 4, 6, 8, 10)
scala> seats ++ List(10, 12)
val res3: List[Int] = List(2, 2, 4, 4, 6, 8, 10, 12)
scala> seats(4)
val res4: Int = 6
In chapter 2 I said I’d tell you how to read operators like these. :: is read “cons” and puts an element on the front of a list. :+ is read “append” and is the appended method from chapter 3 under another name. ++ is “concat” and joins two collections. None of them changed seats. It still has six elements after more was built from it.
Copying a whole list every time you add to it sounds slow, and more.tail eq seats shows why it isn’t. tail is a list without its first element, and eq is the reference comparison from chapter 2. The answer is true: the tail of more is the very same object as seats. Because a List is a linked list, putting 10 on the front only made one new cell, which points at the existing list. That sharing is only safe because neither list can ever change.
Working at the other end of a List is slower. :+ has to copy the whole list, and seats(4) has to walk along it to reach the fifth element. For a few dozen bookings that doesn’t matter. For a long sequence that you append to or index into, use Vector, which works like List apart from :: and does both quickly. You’ll mostly see List in Scala code, with Vector where it’s needed and Seq, a type that covers both, in method signatures that don’t mind which they get.
4.9. Mutable and Java collections
Scala has mutable collections as well, in the package scala.collection.mutable. Converting between Scala’s collections and Java’s, in either direction, takes one import:
scala> import scala.jdk.CollectionConverters.*
scala> val fromJava = java.util.List.of(2, 4, 6).asScala.toList
val fromJava: List[Int] = List(2, 4, 6)
scala> fromJava.asJava
val res0: java.util.List[Int] = [2, 4, 6]
scala> val buffer = scala.collection.mutable.ArrayBuffer(2, 4)
val buffer: collection.mutable.ArrayBuffer[Int] = ArrayBuffer(2, 4)
scala> buffer += 6
val res1: collection.mutable.ArrayBuffer[Int] = ArrayBuffer(2, 4, 6)
scala> buffer.toList
val res2: List[Int] = List(2, 4, 6)
Since asScala and asJava wrap the collection they’re given instead of copying it, they’re quick to call at the point where your code meets a Java library. What asScala returns is a view of the Java list, which can still change underneath you. That’s why the example copies it into a List with toList straight away. ArrayBuffer is the counterpart of Java’s ArrayList. Its += adds an element in place. A mutable collection is a reasonable choice inside one method that’s building something up step by step. Convert it with toList before handing the result to anyone else.
4.10. The last table at eight
Chapter 1 mentioned two people asking for the last table at eight o’clock at the same moment. We now have enough code to get that wrong. Add a method to availability.scala that makes a booking:
def reserve(store: BookingStore, party: Party, time: LocalTime): String =
val candidates = freeAt(time, store.all).filter(_.seats >= party.size)
if candidates.isEmpty then s"${party.name}: sorry, nothing free at $time"
else
val table = candidates.minBy(_.seats)
Thread.sleep(300)
store.add(Booking(party, table, time, Status.Confirmed))
s"${party.name}: table ${table.number} at $time"
reserve picks the smallest free table that’s big enough and adds a confirmed booking to the store. The Thread.sleep represents the time a real system spends between checking and saving, on a call to a database for instance. I’ve made it 300 milliseconds, far longer than is realistic, so that the program below does the same thing on every run.
Then add a second @main to main.scala:
@main def lastTable(): Unit =
val eight = LocalTime.of(20, 0)
val store = InMemoryBookingStore()
for table <- Table.all.filter(_.number != 6) do
store.add(Booking(Party("Regular", table.seats), table, eight, Status.Seated))
println(s"Free at $eight: ${freeAt(eight, store.all).map(_.number)}")
var toIbrahim = ""
var toCastellanos = ""
val first = Thread(() => toIbrahim = reserve(store, Party("Ibrahim", 7), eight))
val second = Thread(() => toCastellanos = reserve(store, Party("Castellanos", 8), eight))
first.start()
Thread.sleep(100)
second.start()
first.join()
second.join()
println(toIbrahim)
println(toCastellanos)
val onTableSix = store.at(eight).filter(_.table.number == 6).map(_.party.name)
println(s"Table 6 at $eight: $onTableSix")
The program fills every table except number 6 for eight o’clock. Then two parties who both need table 6 try to book it from separate Java threads, the second starting a tenth of a second after the first. A Scala lambda can be passed where a Runnable is wanted, as a Java lambda can. Each thread’s answer goes into a var so that both can be printed in a fixed order at the end. Scala lets a lambda assign to a local var, where Java would insist on an effectively final variable.
$ scala run . --main-class fullybooked.lastTable
Free at 20:00: List(6)
Ibrahim: table 6 at 20:00
Castellanos: table 6 at 20:00
Table 6 at 20:00: List(Ibrahim, Castellanos)
Both parties have been told they’ve got table 6, and the store holds both bookings. Each thread looked before the other had saved, so each saw table 6 free and went ahead. Java code written the same way would have the same bug. Immutable lists don’t prevent it: the list in the store never changes, but the var that points at it does change, and the check and the booking are two separate steps.
add has a second bug of the same kind. Two threads can each read the same list, append to it and store their own result, in which case the later one overwrites the earlier. While I was trying different timings for this example, some runs ended with only one of the two bookings in the store.
The sleeps only fix the timing, so that the double booking shows on every run, and both bugs would be there without them. In a real system the gap between checking and saving is much shorter. The double booking then needs two requests to arrive inside that gap, which on a busy night they eventually will. This problem comes back in chapters 14, 17 and 20, each of which fixes it in a different way.
4.11. Exercises
Solutions are in the book’s downloadable code, under ch04/exercises.
-
Work out the total deposit due tonight from the parties that hold a table.
sumworks on a list ofBigDecimal. -
List the names of the parties arriving at eight or later, in order of arrival.
-
Count how many bookings there are in each status. The result should be a
Map. -
Which tables are booked more than once tonight?
filteron aMaptakes a two-argument lambda asmapdoes, andkeysgives you the keys of what’s left. -
Predict the results of
List[Int]().forall(_ > 5)andList[Int]().exists(_ > 5), then try them.List[Int]()is an empty list of integers. -
Take the
Thread.sleep(300)out ofreserveand runlastTableseveral times. Then take theThread.sleep(100)out oflastTableas well and run it several more. What changes each time, and why? -
Write
freeFor(party: Party, time: LocalTime, bookings: List[Booking]): List[Table], which returns the tables that are big enough and stay free for the party’s whole visit. Two time ranges overlap when each starts before the other ends.