Файл: Programming_in_Scala,_2nd_edition.pdf

for ( seq ) yield expr

Here, 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 n

This for expression contains one generator, one definition, and one filter. As mentioned in Section 7.3 on page 167, you can also enclose the sequence in braces instead of parentheses. Then the semicolons become optional:

A generator is of the form:

pat <- expr

The 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 = expr

This definition binds the pattern pat to the value of expr. So it has the same effect as a val definition:

val x = expr

The 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:

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

if expr

Here, 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)

res3: List[(Int, java.lang.String)] = List((1,one), (1,two), (2,one), (2,two))

23.2 The n-queens problem

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 N squares, where the size N is arbitrary. We’ll start numbering cells at one, so the upper-left cell of an N 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

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

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 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 :: queens

placeQueens(n)

}

The 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.

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

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

one such solution: place no queen at all. This solution is represented 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:

1.If the two queens have the same row coordinate,

2.If the two queens have the same column coordinate,

3.If the two queens are on the same diagonal, i.e., the difference between their rows and the difference between their columns are the same.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

The first case, that the two queens have the same row coordinate, cannot happen in the application because placeQueens already takes care to place each queen in a different row. So you could remove the test without changing the functionality of the program as a whole.

23.3 Querying with for expressions

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"

)

)

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

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

res4: 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

res5: 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

res6: 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](xs: List[A])List[A]

scala> removeDuplicates(res6)

res7: List[String] = List(Ullman, Jeffrey)

It’s worth noting that the last expression in method removeDuplicates can be equivalently expressed using a for expression:

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index