Scala Saturday – The Option Type, Part 1

It’s like that time you played basketball in the living room. You knew you should never have done it. But it was just so tempting! And how did that work out for you? Broken lamp? Hole in the wall? And, if you grew up in a house like mine, a tanned hide to follow. You could have avoided it all: the property damage, the wounded pride, the tender backside.

That’s what playing with null is like. You know you shouldn’t, but it’s just so easy! Then you get burned in the end.

The Problem with Null

The problem with null is that it can crop up anywhere an object can. Consider a function that returns a string. This is always OK, right?

val foo: () => String = // ...
val len = foo().length // No worries?

It certainly is in this case:

val foo: () => String = () => "foo"
val len = foo().length
// len: Int = 3

But what about this?

val foo: () => String = () => null
val len = foo().length
// java.lang.NullPointerException !!!

Yeah, not so much. And the problem is that the compiler cannot help us: null is a perfectly legal return value.

We need better semantics! A return type of String ought to guarantee me that I get a String. An empty string would be fine; it just needs to be a String!

Even the guy who invented the concept of null has regretted it:

I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler.

But I couldn’t resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

Sir Charles Antony Richard “Tony” Hoare
Turing Award Winner, Inventor of the Quicksort
Null References: The Billion Dollar Mistake (2009)

Fine! All this lamenting that null is a bad idea is great, but don’t you need a way to represent the idea that sometimes a function may not return a result, or at least, not what you would consider a valid result? That’s what Java maps do: If you call Map.get(key), and that map does not contain an entry for key, you get null. Of course, with most maps, null is a legal value, so you don’t know for certain whether null indicates whether the key was not found or the coder explicitly associated null with that key.

There’s got to be a better way!

Option to the Rescue

When you need to represent the idea that a function may not return a result, use Scala’s Option. You can think of an Option as a bucket (pronounced BUCK-et, not boo-KAY):

The Option type illustrated as a bucket. The bucket may be empty or full. If the Option contains a value (represented by the full bucket), we call it "Some." If the Option does not contain a value (represented by the empty bucket), we call it "None."
The Option Type: Is the Bucket Empty or Full?

When a function returns an Option[T], it may contain a value of type T; it may not. You don’t know until you look into it. It’s Schrödinger’s cat! If the Option is empty, we call it None. If it is full, we call it Some.

The advantage of using Option is that now the compiler can help you out. You cannot assign an Option[T] to a variable of type T. Take this example using List.find:

val opt = (1 to 4).toList.find(_ > 5)
val n : int = opt
// error: not found: type int
//        val n : int = opt

So then, you cannot forget and accidentally assign a null, only to have it bite you later. The compiler reminds you that you need to test the result before trying to use it:

val ns = (1 to 4).toList

val none = ns.find(_ > 5)

if (none.isEmpty) {
  println("None found greater than 5")
} else {
  println(s"Found one greater than 5: ${none.get}")
}
// None found greater than 5

val some = ns.find(_ < 5)
if (some.isEmpty) {
  println("None found less than 5")
} else {
  println(s"Found one less than 5: ${some.get}")
}
// Found one less than 5: 1

Of course, you can override the safeguard, but at least then, you cannot claim ignorance:

val ns = (1 to 4).toList
val none = ns.find(_ > 5)
println(s"Found one greater than 5: ${none.get}")
// java.util.NoSuchElementException: None.get !!!

Next week, we will look at Option some more to see how we can use it in a more functional fashion.

Scala Saturday – The partition Method

The filter function takes a collection and a predicate and returns only the items in a collection that meet the predicate. It discards the ones that don’t.

Well, what if you want to retain all the items in the collection, but you just want them separated into two groups–the sheep from goats, as it were? That’s where partition comes in. The partition operation takes a collection and a predicate, just as filter does, but instead of tossing the items that don’t meet the predicate, partition returns a second collection along with the first: one containing all the items that meet the predicate and one containing all the rest.

Maybe you run a business, and once per quarter, you want to send a message to all your customers. You send a thank you note to the customers that have made a purchase in the last quarter. To the customers who have not, you send a we-miss-you note, perhaps containing a coupon. So then, you need to partition your customer list:

A list of customers, each with a lastPurchase field that is the date of the customer's last purchase, partitioned into two lists. The first list is all customers who have made a purchase in the last three months while the other list contains customers who have not made a purchase in the last three months.
Partitioning a List of Customers Based on the Date of the Latest Purchase

Here is the Customer case class (which uses Java 8’s new LocalDate class):

case class Customer(
  name: String,
  email: String,
  latestPurchase: LocalDate)

Now given a list of customers, here is how you partition that list into those who have made recent purchases and those who have not:

val customers = List(
  Customer("Bob", "bob@bob.com", LocalDate.of(2015, Month.JUNE, 5)),
  Customer("Barb", "barb@barbara.com", LocalDate.of(2015, Month.MAY, 15)),
  Customer("Chuck", "chuck@charles.com", LocalDate.of(2015, Month.JANUARY, 26)),
  Customer("Charlie", "charlie@charlotte.com", LocalDate.of(2015, Month.MARCH, 1)),
  Customer("Dan", "dan@dan.com", LocalDate.of(2014, Month.DECEMBER, 21)),
  Customer("Deb", "deb@deborah.com", LocalDate.of(2015, Month.JANUARY, 24)),
  Customer("Ed", "ed@theodore.com", LocalDate.of(2015, Month.MARCH, 15)),
  Customer("Elle", "elle@elle.com", LocalDate.of(2015, Month.JUNE, 15))
)

val threeMosAgo = LocalDate.now.minusMonths(3)
val (recent, distant) = customers.partition {
  c => c.latestPurchase.isAfter(threeMosAgo)
}
// recent: List[Customer] = List(
//   Customer(Bob,bob@bob.com,2015-06-05),
//   Customer(Barb,barb@barbara.com,2015-05-15), 
//   Customer(Elle,elle@elle.com,2015-06-15))
// distant: List[Customer] = List(
//   Customer(Chuck,chuck@charles.com,2015-01-26),
//   Customer(Charlie,charlie@charlotte.com,2015-03-01),
//   Customer(Dan,dan@dan.com,2014-12-21),
//   Customer(Deb,deb@deborah.com,2015-01-24),
//   Customer(Ed,ed@theodore.com,2015-03-15))

Now you can send that thank you note to each of the customers in the recent list and a miss-you note to each customer in the distant list.

Scala Saturday – The find Method

The Scala collections all define the find function. The find operation traverses a collection and returns the first item in the collection that meets the given condition(s).

Perhaps you are a teacher. You have a type that represents a student with a name and a grade:

case class Student(name: String, grade: Int)

And you have a randomized list of those students:

val students = List(
  Student("Sally", 79),
  Student("Giedrius", 81),
  Student("Aryana", 98),
  Student("Ty", 94),
  Student("Eloise", 86),
  Student("Vergil", 89),
  Student("Doug", 66),
  Student("Delmar", 77),
  Student("Makenna", 88),
  Student("Orval", 93) )

Maybe you want to reward a random A-student (i.e., a student with a grade of 90 or above) with a candy bar. You can use find to return the first A-student in the list:

val scholar = students.find(_.grade >= 90)
// scholar: Option[Student] =
//   Some(Student(Aryana,98))

So, that’s great: Aryana gets a Twix! (It is the only one with the cookie crunch, after all.)

Notice, by the way, that scholar is not a Student, but rather an Option that contains a Student. Let’s get back to that in a minute.

You also happen to be one of those sadistic teachers, though, who likes to embarrass the students who are not living up to their potential. Therefore you pick a random F-student (i.e., with a grade less than 65) and outfit him/her with a dunce cap:

val dunce = students.find(_.grade < 65)
// dunce: Option[Student] = None

Isn’t that interesting? There are no F-students. (Who’s the dunce now?)

That’s the beauty of find: it returns an Option instead of the bare Student. Therefore if no item in the list meets find’s predicate, it does not throw an exception or return null (the way some other languages do). It just returns None. That way, if you write something like this in which you specify that you expect the Student type, Scala does not let you get away with it:

val dunce: Student = students.find(_.grade < 65)
// error: type mismatch;
//  found   : Option[Student]
//  required: Student
//        val dunce: Student = students.find(_.grade < 65)
//                                          ^

It warns you at compile time that you are aiming a firearm at your foot instead of letting you shoot it off at run time with one exception or another.

It could be that you give a test next week that slays the entire class: you may not have an A-student that week. The Option value that find returns makes you test dunce and scholar before you use them to make sure someone is supposed to get a candy bar or a dunce cap before you start handing them out.

Scala Saturday – The sorted, sortBy, and sortWith Methods

You don’t have to program for very long before you need to sort a list of things. Scala’s collections modules are nice enough to give you a canned sorted method.

Maybe you have a list of words, and you want to sort them:

val xs = List(
  "Our", "fathers", "trusted", "in", "You",
  "They", "trusted", "and", "You",
  "delivered", "them")
val sorted = xs.sorted
// sorted: List[String] =
//   List(Our, They, You, You, and,
//        delivered, fathers, in, them,
//        trusted, trusted)

Easy enough. But isn’t that interesting? ‘Y’ words come before ‘A’ words. Or rather, more correctly, ‘Y’ words come before ‘a’ words because, by default, all capital letters are sorted before lowercase letters. And that’s all that sorted does for you: It sorts using the default ordering.

Wouldn’t it be great if you could alter what sort uses to sort by? Well, you can: Use sortBy.

Here’s how to sort this list of words the way your 2nd-grade teacher taught you, that is, without respect to case. Pass sortBy a lambda that returns the lowercase version of each string:

val sortedCaseInsensitive =
  xs.sortBy(_.toLowerCase)
// sortedCaseInsensitive: List[String] =
//   List(and, delivered, fathers, in,
//        Our, them, They, trusted, trusted,
//        You, You)

Or maybe you need to sort a list of words in order of length. Employ a lambda that returns the length of each word:

val sortedByLength = xs.sortBy(_.length)
// sortedByLength: List[String] = 
//   List(in, Our, You, and, You, They,
//        them, fathers, trusted, trusted,
//        delivered)

The sortBy method also works really well for classes. You can use sortBy to specify which member or combination of members to sort by.

Maybe you have a class for album tracks. It has two members: track length (in minutes) and track title.

case class Track(length : Double, name : String)

Let’s say that you have the tracks of Genesis’s Foxtrot:

val ts = List(
  Track(7.35, "Watcher of the Skies"),
  Track(4.783, "Time Table"),
  Track(8.583, "Get 'Em Out by Friday"),
  Track(5.75, "Can-Utility and the Coastliners"),
  Track(1.65, "Horizons"),
  Track(22.95, "Supper's Ready") )

Sort the tracks by track length by passing a lambda to sortBy that returns the length of each track:

val sortedByTrackLength = ts.sortBy(_.length)
// sortedByTrackLength: List[Track] = List(
//   Track(1.65,Horizons),
//   Track(4.783,Time Table), 
//   Track(5.75,Can-Utility and the Coastliners), 
//   Track(7.35,Watcher of the Skies), 
//   Track(8.583,Get 'Em Out by Friday), 
//   Track(22.95,Supper's Ready))

To sort according to track name instead, use a lambda that returns the track name rather than track length:

val sortedByTrackName = ts.sortBy(_.name)
// sortedByTrackName: List[Track] = List(
//   Track(5.75,Can-Utility and the Coastliners), 
//   Track(8.583,Get 'Em Out by Friday), 
//   Track(1.65,Horizons), 
//   Track(22.95,Supper's Ready), 
//   Track(4.783,Time Table), 
//   Track(7.35,Watcher of the Skies))

Another sorting method is sortWith. It differs from sortBy in the kind of lambda that it takes to perform the sorting. Whereas sortBy accepts a function that takes a single element and generates a single value to sort by, sortWith accepts a function that takes two elements as inputs and returns true if the first element is “less than” the second element, or otherwise false. In other words, you define the pairwise comparison.

For example, if you want to sort your list of words from Psalm 22 in reverse, you could do so with sortWith by reversing the comparison—do a greater-than comparison rather than a less-than:

val reversed = xs.sortWith(_ > _)
// reversed: List[String] = List(
//   trusted, trusted, them, in, fathers, 
//   delivered, and, You, You, They, Our)

sortWith is very nice when you need to compare more than one object member. Perhaps you need to sort a list of names according to last name and then first name. The lambda can first compare the last names and then the first names only if necessary:

case class Name(first: String, last: String)
val names = List(
  Name("Phil", "Collins"),
  Name("Jackie", "Collins"),
  Name("Joan", "Collins"),
  Name("Tom", "Collins"),
  Name("George", "Bush"),
  Name("Jeb", "Bush"),
  Name("Neil", "Bush"),
  Name("Marvin", "Bush"))

val lastThenFirst = names.sortWith { (a, b) =>
  if (a.last == b.last) a.first < b.first
  else a.last < b.last
}
// lastThenFirst: List[Name] = List(
//   Name(George,Bush), 
//   Name(Jeb,Bush), 
//   Name(Marvin,Bush), 
//   Name(Neil,Bush), 
//   Name(Jackie,Collins), 
//   Name(Joan,Collins), 
//   Name(Phil,Collins), 
//   Name(Tom,Collins))

Scala Saturday – The foldLeft Method

Last week we looked at the reduce operation, and we observed three properties:

  • Using reduce on an empty collection yields an exception.
  • You can only reduce a collection to a value of the same type as the elements in the collection.
  • The order of the items in the collection (usually) matters.

We also noticed that there are several common operations—sum, product, and string concatenation—that are just special cases of reduce.

As it happens, reduce is itself a special case of a more fundamental operation: foldLeft. Furthermore, while order still matters, foldLeft can

  • handle empty collections, and
  • reduce a collection of one type to a value of a different type.

Why is that? First, foldLeft takes a binary operation just as reduce does, but it also takes a starting value in addition to the collection. That is how foldLeft can handle empty collections. If the collection is empty, you’re just left with the starting value. Second, because you give foldLeft a starting value, that starting value could be of any type; it doesn’t have to match the type of the items in the collection. The reason reduce can only reduce a collection to a value of the same type is because the only starting value it has is the first value in the collection.

Let’s put foldLeft into action.

Our Product Line

We implemented a product operation last week with reduce. Let’s do it this week with foldLeft. This figure illustrates what’s going on:

The foldLeft operation produces the product of the list of integers [5,3,6] by starting with 1 (because 1 times x is always x), multiplying 1 and 5 to get 5, multiplying 5 and 3 to get fifteen, and finally multiplying 15 and 6 to get a final product of 90.
Producing the Product of a List of Integers Using foldLeft

In multiplication, 1 is the identity value. That is, 1 times x is always x. So then, if you want to calculate the product of a list of integers, make your starting value 1. Here is the code:

val product = List(5,3,6).fold(1)(_*_)
// product: Int = 90

Now what if the list is empty? We cannot handle an empty list with reduce, but what does foldLeft do?

val product = List().fold(1)(_*_)
// product: Int = 1

So then, when foldLeft receives an empty collection, it just returns the starting value—in this case, 1.

Stringing You Along

Last week we also implemented List.mkString with reduce. We can do the same thing with foldLeft but there are some gotchas.

Try a straightforward approach:

val illJoined =
  List("do","mi","sol").foldLeft("")(_ + "-" + _)
// illJoined: String = -do-mi-sol

Eek! What happened? You don’t want the extra hyphen on the front! You just want hyphens in between the elements!

What if you have a list with just one item?

val illJoined =
  List("do").foldLeft("")(_ + "-" + _)
// illJoined: String = -do

No better. The following figure shows you what has happened:

The foldLeft operation can concatenate a list of strings together with a separator, but this figure illustrates how the desired result is a little more complicated than it is with reduce. Taking a list of strings ["do", "mi", "sol"], a starting value of an empty string, and a binary operation that concatenates two strings together with a hyphen in the middle, you end up with an extra hyphen at the front of the resulting string. That is because the first application of the binary operation concatenates the empty string with a hyphen and "do". In a join operation, you usually only want the separator between values, so using foldLeft requires some additional checking.
Using foldLeft to Join a List of Strings Together with a Separator

While reduce cannot handle an empty collection, it only starts applying the reduction operation on the first two elements. On the other hand, foldLeft applies the binary operation on the starting value and the first item in the list.

To do mkString right with foldLeft, you have to account for some special cases:

def join(xs: List[String]): String = {
  if (xs.isEmpty) "" 
  else if (xs.length == 1) xs.head
  else xs.tail.foldLeft(xs.head)(_ + "-" + _)
}
val emptyJoined = join(List())
// emptyJoined: String = ""
val singleJoined = join(List("do"))
// singleJoined: String = do
val manyJoined = join(List("do","mi","sol"))
// manyJoined: String = do-mi-sol

From Type to Type

Finally, consider an example of something foldLeft can do that reduce cannot. If reduce receives a list of integers, it can only produce a single integer. If it receives a list of strings, its result is a single string. In contrast, foldLeft can take a list of integers and produce a string. Or it could take a list of strings and produce a list of integers.

For instance, you can use foldLeft to reverse a list:

val reversed =
  (1 to 10).foldLeft(List[Int]()) {
    (xs, x) => x :: xs
  }
// reversed: List[Int] =
//   List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)

Notice how the starting value is a list, but the type of the elements in the input list Int, not List[Int]. Because the starting value can be a type that is different from the type of the input list elements, the binary operation can transform the elements in the list to match the type of the starting value. In fact, that is the constraint with foldLeft: the type of the result must be type of the starting value. If your starting value is a list, foldLeft must return a list. If your starting value is an integer, foldLeft must return an integer.

Another example is determining the length of the longest string in a list of strings:

val longest =
  List(
    "a","borborygmus","sesquipedalian","small"
  ).foldLeft(0) {
    (n,s) => math.max(n, s.length)
  }
// longest: Int = 14

Here is the documentation on foldLeft in each collection module that defines it:

As an exercise, you could try implementing map with foldLeft.

Scala Saturday – The reduce Method

If you have a collection of numbers that you want to sum or multiply together, Scala’s collection classes all define both a sum operation and a product operation:

ScalaDocs for Scala Collection sum and product Methods
Array sum product
List sum product
Seq sum product
Set sum product

But what if, for some reason, you want to implement sum or product yourself? Well, it turns out that sum and product are both just special cases of a more general operation that the collection modules also define: reduce. The reduce operation takes all the elements in a collection and combines them in some way to produce a single value. It uses a binary operation to combine the first two values. Then it takes the result of that first combination and combines it with the next element in the collection, and then the next, and so on through the end of the collection.

Here’s an illustration of how to use reduce to implement a product operation:

Taking a list of [2,5,3,6], reduce multiplies 2 and 5 to produce 10, then 10 and 3 to produce 30, and finally 30 and 6 to get the final result of 180.
Using Reduce to Calculate the Product of All Numbers in a List

The code looks like this:

val product = List(2,5,3,6) reduce {
  (x,y) => x * y
}
// product: Int = 180

You can be even more succinct by employing the underscore, Scala’s shorthand for the lambda’s input arguments:

val product = List(2,5,3,6).reduce(_*_)
// product: Int = 180

Another special case of reduce is mkString, e.g., List.mkString—also known as a join operation—which allows you to concatenate a sequence of values together into a string with a separator between each value. Here’s how it works:

Taking a list of strings ["do","mi","sol","do"], reduce combines "do" and "mi" to produce "do-mi", and then combines "do-mi" and "sol" to produce "do-mi-sol", and finally "do-mi-sol" and "do" to produce the final result of "do-mi-sol-do"
Using Reduce to Join a List of Strings Together with a Separator

See how similar it is to the product operation above? If you should want to implement mkString yourself, you could use reduce like this:

val joined =
  List("do","mi","sol","do") reduce {
    (x,y) => x + "-" + y
  }
// joined: String = do-mi-sol-do

Or again, with the shorthand:

val joined =
  List("do","mi","sol","do").
    reduce(_ + "-" + _)
// joined: String = do-mi-sol-do

Here is the documentation on reduce in each of the collection classes:

Now a few of caveats about reduce:

  • You cannot use reduce on an empty collection. You will get an exception if you do, so make sure you check to make sure your collection is not empty before you pass it to reduce. (Scala provides an alternative, reduceOption, that does not throw an exception, but represents the result as an Option.)

  • The result of a reduce operation is always the same type as the elements in the collection. In other words, you can only reduce a collection of type A to a value of type A. You cannot reduce a collection of type A to a value of type B.

  • Finally, order matters if the order of your binary operation matters. In other words, with addition and multiplication, order does not matter. That is, a + b is the same as b + a. (Mathematicians say that such a function is commutative.) But with something like subtraction, order does matter. In other words, a − b does not necessarily produce the same result as b − a. So make sure that your binary operation applies the reduction to its operands in the correct order.

Having noted these caveats, next week, we will cover the fold operation. It operates almost the same way as reduce in that it walks a collection, applying a binary operation to each element. The fold operation cannot help us with that last point—order still matters—but it can handle an empty collection and, if necessary, produce a result that is of a type different from the type of the source collection’s elements.

Scala Saturday – The Set.intersect Method

Last week we looked at Set.union. This week we look at Set.intersect. When dealing with sets (which, remember, by definition, cannot contain duplicate elements), sometimes you have two sets, and you want to know what elements they have in common. That is called the intersection of two sets.

Maybe you have some crazy password policy:

  • Passwords must be at least 12 characters;
  • Each character must be unique; and
  • New passwords may have no more than four characters in common.

You can use a set intersection to determine whether an old password and a new password have too many characters in common:

val oldPwd = "aU*E3)vn'2-="

val newPwd1 = "Uv0&*n2'EI~5"
val common1 = oldPwd.toSet intersect newPwd1.toSet
// common1: scala.collection.immutable.Set[Char] =
//   Set(E, *, n, U, v, ', 2)
// Too many characters in common!

val newPwd2 = "Uv0&6;2'ZI~/"
val common2 = oldPwd.toSet intersect newPwd2.toSet
// common2: scala.collection.immutable.Set[Char] =
//   Set(U, v, ', 2)
// Just right!

Scala Saturday – The Set.union Method

A defining property of mathematical set is that it contain no duplicates. Sometimes you need to combine two sets. But what if those sets contain some of the same elements, so that the combination would contain duplicates? No worries! That’s where Set.union comes in.

Journey from Mariabronn

The classic lineup of progressive rock band Kansas in the 1970s consisted of Steve Walsh, Kerry Livgren, Rich Williams, Robby Steinhardt, Dave Hope, and Phil Ehart. However, over the years, the lineup changed several times. Currently Kansas are Ronnie Platt, David Manion, Rich Williams, David Ragsdale, Billy Greer, and Phil Ehart.

You can represent these two lineups as sets:

val classicKansas = Set(
  "Walsh", "Livgren", "Williams",
  "Steinhardt", "Hope", "Ehart")
val currentKansas = Set(
  "Platt", "Manion", "Williams",
  "Ragsdale", "Greer", "Ehart")

Magnum Opus

What if the classic Kansas lineup got together with the current Kansas lineup for a reunion tour? How would the omnibus lineup look? Call the first set’s union method, and pass it the second set:

val totalKansas = classicKansas union currentKansas
// totalKansas: scala.collection.immutable.Set[String] =
//   Set(Ehart, Walsh, Steinhardt, Platt, Ragsdale,
//     Manion, Greer, Livgren, Hope, Williams)

Notice how the union of the two sets does not contain duplicates even though Ehart and Williams were in both lineups.

Scala Saturday – The flatMap Method

In a previous Scala Saturday post, we looked at the map method. As a quick review, map lets you take a collection of elements, calculate a new value from each source element, and create a new collection containing those new values. The mapping function has the following signature:

A => B

In other words, the function takes a single value of type A and returns a single value of type B.

But what if you have a mapping function with this signature?

A => List[B]

In other words, this function does not take one value and produce one value. Rather it takes one value and produces multiple values. What if you’re OK with that, but you just need to take those many values returned from each mapping and smash them all together into one list?

From Side to Side

Most of the guys in legendary progressive rock band Yes didn’t have just one job on their Close to the Edge album. They performed multiple duties. So let’s create a Musician case class to represent a musician and the list of instruments he plays on the album:

case class Musician(
  name: String,
  instruments: List[String])

Now you can create a list of musicians:

val yes = List(
  Musician("Jon Anderson", List("vocals")),
  Musician(
    "Steve Howe",
    List("electric guitars", "acoustic guitars",
      "vocals")
  ),
  Musician(
    "Chris Squire",
    List("bass guitar", "acoustic guitars",
      "vocals")
  ),
  Musician(
    "Rick Wakeman",
    List("Hammond organ", "Minimoog",
      "Mellotron", "grand piano",
      "RMI 368 Electra-Piano and Harpsichord",
      "pipe organ at St. Giles, Cripplegate church")
  ),
  Musician(
    "Bill Bruford",
    List("drums", "percussion")
  )
)

Maybe you want one long list of every instrument the fellows in Yes used on the album. You just have to map each musician to his list of instruments, and then concatenate those lists together:

Illustrates mapping a list of musicians (jon, steve, chris, rick, nill) to a list of lists of the instruments that each musician plays ((vocals), (electric guitars, acoustic guitars), (bass guitar, vocals), (Hammond organ, Minimoog, ...), (drums, percussion)) and then a flattening of those nested lists into one long list
Collecting Musicians’ Instruments into One Long List

You could do this with two functions you’ve read about already on Scala Saturdays: map and concat:

val instruments = yes.map(_.instruments).flatten
// instruments: List[String] =
//   List(vocals, electric guitars, acoustic guitars,
//     vocals, bass guitar, ...)

The Total Mass

What if there were a function that could do both of those things—perform the transformation and the concatenation all in one? Turns out that there is: flatMap!

val instruments = yes flatMap (_.instruments)
// instruments: List[String] =
//   List(vocals, electric guitars, acoustic guitars,
//     vocals, bass guitar, ...)

How ’bout that? The very same results all in one function!

So then, flatMap performs a map and a flatten all in one function call.

You’ve seen flatMap examples here only in terms of lists, but the Scala’s other collections define the flatMap method, too:

Scala Saturday – The filter Method

Another frequently used operation in functional programming is filter. The filter method allows you to pare down a collection by specifying a criterion. Any element in the collection that does not meet that criterion is dropped, and you get a new collection consisting only of the elements that meet the criterion.

Sequential Collections

Suppose you have a list of numbers, and you want to filter out the even numbers, leaving only the odds. Define a predicate—a function that takes an input and returns true or false—that determines whether an integer is odd, returning true for odd numbers and false for even. Pass that predicate to your list’s filter method, and List.filter returns a new list containing only the odd numbers:

Illustrates filtering evens out of a list of integers (4, 5, 6, 7) with a predicate that returns true for odd numbers and false for even numbers. This yields the list (5, 7).
Filtering Out the Even Numbers from a List of Numbers

Here is the code:

val f = (n: Int) => n % 2 == 1
// odds: List[Int] = List(5, 7)

Notice that filter preserves the order of the original collection because a list is a sequential collection. The same goes for arrays and sequences.

Sets

While filter works essentially the same for sets as it does for the sequential collections, it does not guarantee to preserve the order. Such is the nature of sets: they are not sequential collections.

If you have a set of words, and you want to retain only the words that do not start with “w,” you take the same approach as with a list. Define a predicate that determines whether a string starts with a letter other than "w". Then pass your predicate to your set’s filter method:

Illustrates filtering a set of words { "weary", "world", "young", "struggle" } to retain only the words that do not begin with "w": { "young", "struggle" }
Retaining Only Words that Don’t Start with “w”

The code ought to look pretty familiar:

val f = (s: String) => !s.startsWith("w")
val nonWWords = Set(
  "weary","world","young","struggle"
) filter f
// nonWWords: scala.collection.immutable.Set[String] =
//   Set(young, struggle)

Again, while the order of the elements happens to have been preserved in this simple example with a small set, Set.filter is not required to do so.

Maps

There is also Map.filter. Instead of taking a single-input predicate, Map.filter takes a two-input predicate: the first input is the map’s key type, and the second is the value type. That means you can filter a map on the key, the value, or both.

Maybe you have a map of Spock’s Beard albums to the members of the band who played on that album. (Spock’s Beard has had some changes in personnel over the years.) You want to know on which albums Ted Leonard was on vocals:

val albums = Map(
  "The Light" -> Set("N. Morse","A. Morse","Meros","D'Virgillio"),
  "Beware of Darkness" -> Set("N. Morse","A. Morse","Okumoto","Meros","D'Virgillio"),
  "The Kindness of Strangers" -> Set("N. Morse","A. Morse","Okumoto","Meros","D'Virgillio"),
  "Day for Night" -> Set("N. Morse","A. Morse","Okumoto","Meros","D'Virgillio"),
  "V" -> Set("N. Morse","A. Morse","Okumoto","Meros","D'Virgillio"),
  "Snow" -> Set("N. Morse","A. Morse","Okumoto","Meros","D'Virgillio"),
  "Feel Euphoria" -> Set("A. Morse","Okumoto","Meros","D'Virgillio"),
  "Octane" -> Set("A. Morse","Okumoto","Meros","D'Virgillio"),
  "Spock's Beard" -> Set("A. Morse","Okumoto","Meros","D'Virgillio"),
  "X" -> Set("A. Morse","Okumoto","Meros","D'Virgillio"),
  "Brief Nocturnes and Dreamless Sleep" -> Set("Leonard","A. Morse","Okumoto","Meros","Keegan")
)
val withLeonard = albums filter { case (_,v) =>
  v contains "Leonard"
}
// withLeonard: scala.collection.immutable.Map[String,scala.collection.immutable.Set[String]] =
//   Map(
//     Brief Nocturnes and Dreamless Sleep ->
//     Set(A. Morse, Leonard, Okumoto, Keegan, Meros))

That’s a big chunk there, but the long and the short is that our filter function is ignoring the key (hence the underscore) and examining only the value, searching the set in each entry for Leonard’s name.

The Map trait also defines a filterKeys method for filtering by key. filterKeys takes a single-input predicate like Set.filter.

Filter … NOT!

In addition to filter, Scala collections also define the filterNot method. It simply takes the filtering function and inverts it so that you get results opposite those of filter.

It’s a matter of style, I suppose, as to whether you prefer to use filterNot or to use filter with a filtering function that you invert yourself. There is an argument to be made that filterNot is more readable: it is sometimes easy to overlook that little ! in a larger expression. Still, it seems like an unnecessary expansion of the API. Furthermore, if you’re going to have both filter and filterNot, why do the collections not provide, e.g., findNot, dropWhileNot, and takeWhileNot—the inverted counterparts of find, dropWhile, and takeWhile?