|
|
Chapter 16 demonstrated that higher-order functions such as map, flatMap, and filter provide powerful constructions for dealing with lists. But sometimes the level of abstraction required by these functions makes a program a bit hard to understand. Here's an example. Say you are given a list of persons, each defined as an instance of a class Person. Class Person has fields indicating the person's name, whether (s)he is male, and his/her children. Here's the class definition:
scala> case class Person(name: String, isMale: Boolean, children: Person*)Here's a list of some sample persons:
val lara = Person("Lara", false) val bob = Person("Bob", true) val julie = Person("Julie", false, lara, bob) val persons = List(lara, bob, julie)Now, say you want to find out the names of all pairs of mothers and their children in that list. Using map, flatMap and filter, you can formulate the following query:
scala> persons filter (p => !p.isMale) flatMap (p => (p.children map (c => (p.name, c.name)))) res5: List[(String, String)] = List((Julie,Lara), (Julie,Bob))The query does its job, but it's not exactly trivial to write or understand. Is there a simpler way? In fact, there is. Remember the for expressions in Section 7.3? Using a for expression, the same example can be written as follows:
scala> for (p <- persons; if !p.isMale; c <- p.children) yield (p.name, c.name) res6: List[(String, String)] = List((Julie,Lara), (Julie,Bob))The result of this expression is exactly the same as the result of the previous expression. What's more, most readers of the code would likely find the for expression much clearer than the previous query, which used the higher-order functions, map, flatMap, and filter.
However, the two queries are not as dissimilar as it might seem. In fact, it turns out that the Scala compiler will translate the second query into the first one. More generally, all for expressions that yield a result are translated by the compiler into combinations of invocations of the higher-order methods map, flatMap, and filter. All for loops without yield are translated into a smaller set of higher-order functions: just filter and foreach.
In this chapter, you'll find out first about the precise rules of writing for expressions. After that, you'll see how they can make combinatorial problems easier to solve. Finally, you'll learn how for expressions are translated, and how as a result, for expressions can help you "grow" the Scala language into new application domains.
Generally, a for expression is of the form:
for ( seq ) yield exprHere, seq is a sequence of generators, definitions and filters, with semicolons between successive elements. An example is the for expression:
for (p <- persons; n = p.name; if (n startsWith "To")) yield nThe for expression above contains one generator, one definition, and one filter. As mentioned in Section 7.3, you can also enclose the sequence in braces instead of parentheses, then the semicolons become optional:
for { p <- persons // a generator n = p.name // a definition if (n startsWith "To") // a filter } yield nA generator is of the form:
pat <- exprThe expression expr typically returns a list, even though you will see later that this can be generalized. The pattern pat gets matched one-by-one against all elements of that list. If the match succeeds, the variables in the pattern get bound to the corresponding parts of the element, just the way it is described in Chapter 15. But if the match fails, no MatchError is thrown. Instead, the element is simply discarded from the iteration.
In the most common case, the pattern pat is just a variable x, as in x <- expr. In that case, the variable x simply iterates over all elements returned by expr.
A definition is of the form:
pat = exprThis definition binds the pattern pat to the value of expr. So it has the same effect as a val definition:
val x = exprThe most common case is again where the pattern is a simple variable x, e.g., x = expr. This defines x as a name for the value expr.
A filter is of the form:
if exprHere, expr is an expression of type Boolean. The filter drops from the iteration all elements for which expr returns false.
Every for expression starts with a generator. If there are several generators in a for expression, later generators vary more rapidly than earlier ones. You can verify this easily with the following simple test:
scala> for (x <- List(1, 2); y <- List("one", "two")) yield (x, y) res0: List[(Int, java.lang.String)] = List((1,one), (1,two), (2,one), (2,two))
A particularly suitable application area of for expressions are combinatorial puzzles. An example of such a puzzle is the 8-queens problem: Given a standard chess-board, place eight queens such that no queen is in check from any other (a queen can check another piece if they are on the same column, row, or diagonal). To find a solution to this problem, it's actually simpler to generalize it to chess-boards of arbitrary size. Hence, the problem is to place N queens on a chess-board of N \times N squares, where the size N is arbitrary. We'll start numbering cells at one, so the upper-left cell of an N \times N board has coordinate (1, 1), and the lower-right cell has coordinate (N, N).
To solve the N-queens problem, note that you need to place a queen in each row. So you could place queens in successive rows, each time checking that a newly placed queen is not in check from any other queens that have already been placed. In the course of this search, it might arrive that a queen that needs to be placed in row k would be in check in all fields of that row from queens in row 1 to k-1. In that case, you need to abort that part of the search in order to continue with a different configuration of queens in columns 1 to k-1.
An imperative solution to this problem would place queens one by one, moving them around on the board. But it looks difficult to come up with a scheme that really tries all possibilities.
A more functional approach represents a solution directly, as a value. A solution consists of a list of coordinates, one for each queen placed on the board.
Note, however, that a full solution can not be found in a single step. It needs to be built up gradually, by occupying successive rows with queens.
This suggests a recursive algorithm. Assume you have already generated all solutions of placing k queens on a board of size N \times N, where k is less than N. Each such solution can be presented by a list of length k of coordinates (row, column), where both row and column numbers range from 1 to N. It's convenient to treat these partial solution lists as stacks, where the coordinates of the queen in row k come first in the list, followed by the coordinates of the queen in row k-1, and so on. The bottom of the stack is the coordinate of the queen placed in the first row of the board. All solutions together are represented as a list of lists, with one element for each solution.
Now, to place the next queen in row k+1, generate all possible extensions of each previous solution by one more queen. This yields another list of solution lists, this time of length k+1. Continue the process until you have obtained all solutions of the size of the chess-board N. This algorithmic idea is embodied in function placeQueens below:
def queens(n: Int): List[List[(Int, Int)]] = { def placeQueens(k: Int): List[List[(Int, Int)]] = if (k == 0) List(List()) else for { queens <- placeQueens(k - 1) column <- 1 to n queen = (k, column) if isSafe(queen, queens) } yield queen :: queensThe outer function queens in the program above simply calls placeQueens with the size of the board n as its argument. The task of the function application placeQueens(k) is to generate all partial solutions of length k in a list. Every element of the list is one solution, represented by a list of length k. So placeQueens returns a list of lists.
placeQueens(n) }
If the parameter k to placeQueens is 0, this means that it needs to generate all solutions of placing zero queens on zero rows. There is exactly one such solution: place no queen at all. This is represented as a solution by the empty list. So if k is zero, placeQueens returns List(List()), a list consisting of a single element that is the empty list. Note that this is quite different from the empty list List(). If placeQueens returns List(), this means no solutions, instead of a single solution consisting of no placed queens.
In the other case, where k is not zero, all the work of placeQueens is done in a for expression. The first generator of that for expression iterates through all solutions of placing k - 1 queens on the board. The second generator iterates through all possible columns on which the k'th queen might be placed. The third part of the for expression defines the newly considered queen position to be the pair consisting of row k and each produced column. The fourth part of the for expression is a filter which checks with isSafe whether the new queen is safe from check of all previous queens (the definition of isSafe will be discussed a bit later).
If the new queen is not in check from any other queens, it can form part of a partial solution, so placeQueens generates with queen :: queens a new solution. If the new queen is not safe from check, the filter returns false, so no solution is generated.
The only remaining bit is the isSafe method, which is used to check whether a given queen is in check from any other element in a list of queens. Here is its definition:
def isSafe(queen: (Int, Int), queens: List[(Int, Int)]) = queens forall (q => !inCheck(queen, q))The isSafe method expresses that a queen is safe with respect to some other queens if it is not in check from any other queen. The inCheck method expresses that queens q1 and q2 are mutually in check. It returns true in one of three cases:
def inCheck(q1: (Int, Int), q2: (Int, Int)) = q1._1 == q2._1 || // same row q1._2 == q2._2 || // same column (q1._1 - q2._1).abs == (q1._2 - q2._2).abs // on diagonal
The for notation is essentially equivalent to common operations of database query languages. For instance, say you are given a database named books, represented as a list of books, where Book is defined as follows:
case class Book(title: String, authors: String*)Here is a small example database, represented as an in-memory list:
val books: List[Book] = List( Book( "Structure and Interpretation of Computer Programs", "Abelson, Harold", "Sussman, Gerald J." ), Book( "Principles of Compiler Design", "Aho, Alfred", "Ullman, Jeffrey" ), Book( "Programming in Modula-2", "Wirth, Niklaus" ), Book( "Elements of ML Programming", "Ullman, Jeffrey" ), Book( "The Java Language Specification", "Gosling, James", "Joy, Bill", "Steele, Guy", "Bracha, Gilad" ) )Then, to find the titles of all books whose author's last name is "Gosling":
scala> for (b <- books; a <- b.authors if a startsWith "Gosling") yield b.title res0: List[String] = List(The Java Language Specification)Or, to find the titles of all books that have the string "Program" in their title:
scala> for (b <- books if (b.title indexOf "Program") >= 0) yield b.title res4: List[String] = List(Structure and Interpretation of Computer Programs, Programming in Modula-2, Elements of ML Programming)Or, to find the names of all authors that have written at least two books in the database:
scala> for (b1 <- books; b2 <- books if b1 != b2; a1 <- b1.authors; a2 <- b2.authors if a1 == a2) yield a1 res5: List[String] = List(Ullman, Jeffrey, Ullman, Jeffrey)The last solution is not yet perfect, because authors will appear several times in the list of results. You still need to remove duplicate authors from result lists. This can be achieved with the following function:
scala> def removeDuplicates[A](xs: List[A]): List[A] = { if (xs.isEmpty) xs else xs.head :: removeDuplicates( xs.tail filter (x => x != xs.head) ) } removeDuplicates: [A](List[A])List[A]It's worth noting that the last expression in method removeDuplicates can be equivalently expressed using a for expression:
scala> removeDuplicates(res5) res6: List[java.lang.String] = List(Ullman, Jeffrey)
xs.head :: removeDuplicates( for (x <- xs.tail if x != xs.head) yield x )
Every for expression can be expressed in terms of the three higher-order functions map, flatMap and filter. This section describes the translation scheme, which is also used by the Scala compiler.
First, assume you have a simple for expression:
for (x <- expr_1) yield expr_2where x is a variable. Such an expression is translated to:
expr_1.map(x => expr_2)
Now, consider for expressions that combine a leading generator with some other elements. A for expression of the form:
for (x <- expr_1 if expr_2) yield expr_3is translated to:
for (x <- expr_1 filter (x => expr_2)) yield expr_3This translation gives another for expression that is shorter by one element than the original, because an if element is transformed into an application of filter on the first generator expression. The translation then continues with this second expression, so in the end you obtain:
expr_1 filter (x => expr_2) map (x => expr_3)The same translation scheme also applies if there are further elements following the filter. If seq is an arbitrary sequence of generators, definitions and filters, then:
for (x <- expr_1 if expr_2; seq) yield expr_3is translated to:
for (x <- expr_1 filter expr_2; seq) yield expr_3Then translation continues with the second expression, which is again shorter by one element than the original one.
The next case handles for expressions that start with two filters, as in:
for (x <- expr_1; y <- expr_2; seq) yield expr_3Again, assume that seq is an arbitrary sequence of generators, definitions and filters. In fact, seq might also be empty, and in that case there would not be a semicolon after expr_2. The translation scheme stays the same in each case. The for expression above is translated to an application of flatMap:
expr_1.flatMap(x => for (y <- expr_2; seq) yield expr_3)This time, there is another for expression in the function value passed to flatMap. That for expression (which is again simpler by one element than the original) is in turn translated with the same rules.
The three translation schemes given so far are sufficient to translate all for expressions that contain just generators and filters, and where generators bind only simple variables. Take for instance the query, "find all authors who have published at least two books," from Section 23.3:
for (b1 <- books; b2 <- books if b1 != b2; a1 <- b1.authors; a2 <- b2.authors if a1 == a2) yield a1This query translates to the following map/flatMap/filter combination:
books flatMap (b1 => books filter (b2 => b1 != b2) flatMap (b2 => b1.authors flatMap (a1 => b2.authors filter (a2 => a1 == a2) map (a2 => a1))))The translation scheme presented so far does not yet handle generators that that bind whole patterns instead of simple variables. It also does not yet cover definitions. These two aspects will be explained in the next two sub-sections.
The translation scheme becomes more complicated if the left hand side of generator is a pattern, pat, other than a simple variable. Still relatively easy to handle is the case where the for expression binds a tuple of variables. In that case, almost the same scheme as for single variables applies. A for expression of the form:
for ((x_1, ..., x_n) <- expr_1) yield expr_2translates to:
expr_1.map { case (x_1, ..., x_n) => expr_2 }Things become a bit more involved if the left hand side of the generator is an arbitrary pattern pat instead of a single variable or a tuple. In this case:
for (pat <- expr_1) yield expr_2translates to:
expr_1 filter { case pat => true case _ => false } map { case pat => expr_2 }That is, the generated items are first filtered and only those that match pat are mapped. Therefore, it's guaranteed that a pattern-matching generator will never throw a MatchError
The scheme above only treated the case where the for expression contains a single pattern-matching generator. Analogous rules apply if the for expression contains other generators, filters, or definitions. Because these additional rules don't add much new insight, they are omitted from discussion here. If you are interested, you can look them up in the Scala Language Specification sls.
The last missing situation is where a for expression contains embedded definitions. Here's a typical case:
for (x <- expr_1; y = expr_2; seq) yield expr_3Assume again that seq is a (possibly empty) sequence of generators, definitions, and filters. This expression is translated to the following one:
for ((x, y) <- for (x <- expr_1) yield (x, expr_2); seq) yield expr_3So you see that expr_2 is evaluated each time there is a new x value being generated. This re-evaluation is necessary, because expr_2 might refer to x and so needs to be re-evaluated for changing values of x. For you as a programmer the conclusion is that it's probably not a good idea to have definitions embedded in for expressions that do not refer to variables bound by some preceding generator, because re-evaluating such expressions would be wasteful. For instance, instead of:
for (x <- 1 to 1000; y = expensiveComputationNotInvolvingX) yield x * yit's usually better to write:
val y = expensiveComputationNotInvolvingX for (x <- 1 to 1000) yield x * y
The previous subsections showed how for expressions that contain a yield are translated. What about for loops that simply perform a side effect without returning anything? Their translation is similar, but simpler than for expressions. In principle, wherever the previous translation scheme used a map or a flatMap in the translation, the translation scheme for for loops uses just a foreach. For instance, the expression:
for (x <- expr_1) bodytranslates to:
expr_1 foreach (x => body)A larger example is the expression:
for (x <- expr_1; if expr_2; y <- expr_3) bodyThis expression translates to:
expr_1 filter (x => expr_2) foreach (x => expr_3 foreach (y => body))For example, the following expression sums up all elements of a matrix represented as a list of lists:
var sum = 0 for (xs <- xss; x <- xs) sum += xThis loop is translated into two nested foreach applications:
var sum = 0 xss foreach (xs => xs foreach (x => sum += x))
The previous section showed that for expressions can be translated into applications of the higher-order functions map, flatMap, and filter. In fact, you could equally well go the other way: every application of a map, flatMap, or filter can be represented as a for expression. Here are implementations of the three methods in terms of for expressions. The methods are contained in an object Demo, to distinguish them from the standard operations on Lists. To be concrete, the three functions all take a List as parameter, but the translation scheme would work just as well with other collection types:
object Demo { def map[A, B](xs: List[A], f: A => B): List[B] = for (x <- xs) yield f(x)Not surprisingly, the translation of the for expression used in the body of Demo.map will produce a call to map in class List. Similarly, Demo.flatMap and Demo.filter translate to flatMap and filter in class List.
def flatMap[A, B](xs: List[A], f: A => List[B]): List[B] = for (x <- xs; y <- f(x)) yield y
def filter[A](xs: List[A], p: A => Boolean): List[A] = for (x <- xs if p(x)) yield x }
So this little demonstration has shown that for expressions really are equivalent in their expressiveness to applications of the three functions map, flatMap, and filter.
Because the translation of for expressions only relies on the presence of methods map, flatMap, and filter, it is possible to apply the for notation to a large class of data types.
You have already seen for expressions over lists and arrays. These are supported because lists, as well as arrays, define operations map, flatMap, and filter. Because they define a foreach method as well, for loops over these data types are also possible.
Besides lists and arrays, there are also many other types in the Scala standard library that support the same four methods and therefore allow for expressions. Examples are ranges, iterators, streams, and all implementations of sets. It's also perfectly possible for your own data types to support for expressions by defining the necessary methods. To support the full range of for expressions and for loops, you need to define map, flatMap, filter, and foreach as methods of your data type. But it's also possible to define a subset of these methods, and thereby support a subset of all possible for expressions or loops. Here are the precise rules:
Nevertheless, there is a typical setup that captures the most common intention of the higher order methods to which for expressions translate. Say you have a parameterized class, C, which typically would stand for some sort of collection. Then it's quite natural to pick the following type signatures for map, flatMap, filter, and foreach:
abstract class C[A] { def map[B](f: A => B): C[B] def flatMap[B](f: A => C[B]): C[B] def filter(p: A => Boolean): C[A] def foreach(b: A => Unit): Unit }That is, the map function takes a function from the collection's element type A to some other type B. It produces a new collection of the same kind C, but with B as the element type. The flatMap method takes a function f from A to some C-collection of Bs and produces a C-collection of Bs. The filter method takes a predicate function from the collection's element type A to Boolean. It produces a collection of the same type as the one on which it is invoked. Finally, the foreach method takes a function from A to Unit, and produces a Unit result.
Concentrating on just the first three functions, the following facts are noteworthy. In functional programming, there's a general concept called a monad, which can explain a large number of types with computations, ranging from collections, to computations with state and I/O, backtracking computations, and transactions, to name but a few. You can formulate functions map, flatMap, and filter on a monad, and, if you do, they end up having exactly the types given above. Furthermore, you can characterize every monad by map, flatMap, and filter, plus a "unit" constructor that produces a monad from an element value. In an object-oriented language, this "unit" constructor is simply an instance constructor or a factory method. Therefore, map, flatMap and filter can be seen as an object-oriented version of the functional concept of monad. Because for expressions are equivalent to applications of these three methods, they can be seen as syntax for monads.
All this suggests that the concept of for expression is something more general than just iteration over a collection, and indeed it is. For instance, for expressions also play an important role in asynchronous I/O, or as an alternative notation for optional values. Watch out in the Scala libraries for occurrences of map, flatMap, and filter—wherever they are present, for expressions suggest themselves as a concise way of manipulating elements of the type.
In this chapter, you were given a peek under the hood of for expressions and for loops. You learned that they translate into applications of a standard set of higher-order methods. As a consequence of this, you saw that for expressions are really much more general than mere iterations over collections, and that you can design your own classes to support them.