Файл: Programming_in_Scala,_2nd_edition.pdf

list that should be sorted. As another example, here’s how you could define a function that sorts a list of integers in reverse numerical order:

scala> val reverseIntSort = msort((x: Int, y: Int) => x > y) _

reverseIntSort: (List[Int]) => List[Int] = <function>

Because you provided the comparison function already via currying, you now need only provide the list to sort when you invoke the intSort or reverseIntSort functions. Here are some examples:

scala> val mixedInts = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7) mixedInts: List[Int] = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7)

scala> intSort(mixedInts)

res0: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> reverseIntSort(mixedInts)

res1: List[Int] = List(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

16.7Higher-order methods on class List

Many operations over lists have a similar structure. Several patterns appear time and time again. Some examples are: transforming every element of a list in some way, verifying whether a property holds for all elements of a list, extracting from a list elements satisfying a certain criterion, or combining the elements of a list using some operator. In Java, such patterns would usually be expressed by idiomatic combinations of for or while loops. In Scala, they can be expressed more concisely and directly using higher-order operators,6 which are implemented as methods in class List. These higherorder operators are discussed in this section.

Mapping over lists: map, flatMap and foreach

The operation xs map f takes as operands a list xs of type List[T] and a function f of type T => U. It returns the list resulting from applying the function f to each list element in xs. For instance:

6By higher-order operators, we mean higher-order functions used in operator notation. As mentioned in Section 9.1, higher-order functions are functions that take other functions as parameters.

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

scala> List(1, 2, 3) map (_ + 1) res32: List[Int] = List(2, 3, 4)

scala> val words = List("the", "quick", "brown", "fox") words: List[java.lang.String] = List(the, quick, brown, fox)

scala> words map (_.length)

res33: List[Int] = List(3, 5, 5, 3)

scala> words map (_.toList.reverse.mkString) res34: List[String] = List(eht, kciuq, nworb, xof)

The flatMap operator is similar to map, but it takes a function returning a list of elements as its right operand. It applies the function to each list element and returns the concatenation of all function results. The difference between map and flatMap is illustrated in the following example:

scala> words map (_.toList)

res35: List[List[Char]] = List(List(t, h, e), List(q, u, i, c, k), List(b, r, o, w, n), List(f, o, x))

scala> words flatMap (_.toList)

res36: List[Char] = List(t, h, e, q, u, i, c, k, b, r, o, w, n, f, o, x)

You see that where map returns a list of lists, flatMap returns a single list in which all element lists are concatenated.

The differences and interplay between map and flatMap are also demonstrated by the following expression, which constructs a list of all pairs (i; j) such that 1 j < i < 5:

scala> List.range(1, 5) flatMap (

i => List.range(1, i) map (j => (i, j))

)

res37: List[(Int, Int)] = List((2,1), (3,1), (3,2), (4,1), (4,2), (4,3))

List.range is a utility method that creates a list of all integers in some range. It is used twice in this example: once to generate a list of integers from 1 (including) until 5 (excluding), and in a second time to generate a list of integers from 1 until i, for each value of i taken from the first list. The map in this expression generates a list of tuples (i; j) where j < i. The outer

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

flatMap in this example generates this list for each i between 1 and 5, and then concatenates all the results.

Note that the same list can alternatively be constructed with a for expression:

for (i <- List.range(1, 5); j <- List.range(1, i)) yield (i, j)

You’ll learn more about the interplay of for expressions and list operations in Chapter 23.

The third map-like operation is foreach. Unlike map and flatMap, however, foreach takes a procedure (a function with result type Unit) as right operand. It simply applies the procedure to each list element. The result of the operation itself is again Unit; no list of results is assembled. As an example, here is a concise way of summing up all numbers in a list:

scala> var sum = 0 sum: Int = 0

scala> List(1, 2, 3, 4, 5) foreach (sum += _)

scala> sum res39: Int = 15

Filtering lists: filter, partition, find, takeWhile, dropWhile, and span

The operation “xs filter p” takes as operands a list xs of type List[T] and a predicate function p of type T => Boolean. It yields the list of all elements x in xs for which p(x) is true. For instance:

scala> List(1, 2, 3, 4, 5) filter (_ % 2 == 0) res40: List[Int] = List(2, 4)

scala> words filter (_.length == 3)

res41: List[java.lang.String] = List(the, fox)

The partition method is like filter, but it returns a pair of lists. One list contains all elements for which the predicate is true, while the other list contains all elements for which the predicate is false. It is defined by the equality:

xs partition p equals (xs filter p, xs filter (!p(_)))

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

Here’s an example:

scala> List(1, 2, 3, 4, 5) partition (_ % 2 == 0)

res42: (List[Int], List[Int]) = (List(2, 4),List(1, 3, 5))

The find method is also similar to filter but it returns the first element satisfying a given predicate, rather than all such elements. The operation xs find p takes a list xs and a predicate p as operands. It returns an optional value. If there is an element x in xs for which p(x) is true, Some(x) is returned. Otherwise, p is false for all elements, and None is returned. Here are some examples:

scala> List(1, 2, 3, 4, 5) find (_ % 2 == 0) res43: Option[Int] = Some(2)

scala> List(1, 2, 3, 4, 5) find (_ <= 0) res44: Option[Int] = None

The takeWhile and dropWhile operators also take a predicate as their right operand. The operation xs takeWhile p takes the longest prefix of list xs such that every element in the prefix satisfies p. Analogously, the operation xs dropWhile p removes the longest prefix from list xs such that every element in the prefix satisfies p. Here are some examples:

scala> List(1, 2, 3, -4, 5) takeWhile (_ > 0) res45: List[Int] = List(1, 2, 3)

scala> words dropWhile (_ startsWith "t")

res46: List[java.lang.String] = List(quick, brown, fox)

The span method combines takeWhile and dropWhile in one operation, just like splitAt combines take and drop. It returns a pair of two lists, defined by the equality:

xs span p equals (xs takeWhile p, xs dropWhile p)

Like splitAt, span avoids traversing the list xs twice:

scala> List(1, 2, 3, -4, 5) span (_ > 0)

res47: (List[Int], List[Int]) = (List(1, 2, 3),List(-4, 5))

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

Predicates over lists: forall and exists

The operation xs forall p takes as arguments a list xs and a predicate p. Its result is true if all elements in the list satisfy p. Conversely, the operation xs exists p returns true if there is an element in xs that satisfies the predicate p. For instance, to find out whether a matrix represented as a list of lists has a row with only zeroes as elements:

scala> def hasZeroRow(m: List[List[Int]]) =

m exists (row => row forall (_ == 0)) hasZeroRow: (m: List[List[Int]])Boolean

scala> hasZeroRow(diag3) res48: Boolean = false

Folding lists: /: and :\

Another common kind of operation combines the elements of a list with some operator. For instance:

sum(List(a, b, c)) equals 0 + a + b + c

This is a special instance of a fold operation:

scala> def sum(xs: List[Int]): Int = (0 /: xs) (_ + _) sum: (xs: List[Int])Int

Similarly:

product(List(a, b, c)) equals 1 * a * b * c

is a special instance of this fold operation:

scala> def product(xs: List[Int]): Int = (1 /: xs) (_ * _) product: (xs: List[Int])Int

A fold left operation “(z /: xs) (op)” involves three objects: a start value z, a list xs, and a binary operation op. The result of the fold is op applied between successive elements of the list prefixed by z. For instance:

(z /: List(a, b, c)) (op) equals op(op(op(z, a), b), c)

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

Or, graphically:

op

op c

op b

z a

Here’s another example that illustrates how /: is used. To concatenate all words in a list of strings with spaces between them and in front, you can write this:

scala> ("" /: words) (_ +" "+ _)

res49: java.lang.String = the quick brown fox

This gives an extra space at the beginning. To remove the space, you can use this slight variation:

scala> (words.head /: words.tail) (_ +" "+ _) res50: java.lang.String = the quick brown fox

The /: operator produces left-leaning operation trees (its syntax with the slash rising forward is intended to be a reflection of that). The operator has :\ as an analog that produces right-leaning trees. For instance:

(List(a, b, c) :\ z) (op) equals op(a, op(b, op(c, z)))

Or, graphically:

op

a op

b op

c z

The :\ operator is pronounced fold right. It involves the same three operands as fold left, but the first two appear in reversed order: The first operand is the list to fold, the second is the start value.

For associative operations, fold left and fold right are equivalent, but there might be a difference in efficiency. Consider for instance an operation corresponding to the flatten method, which concatenates all elements in a list of lists. This could be implemented with either fold left or fold right:

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

def flattenLeft[T](xss: List[List[T]]) = (List[T]() /: xss) (_ ::: _)

def flattenRight[T](xss: List[List[T]]) = (xss :\ List[T]()) (_ ::: _)

Because list concatenation, xs ::: ys, takes time proportional to its first argument xs, the implementation in terms of fold right in flattenRight is more efficient than the fold left implementation in flattenLeft. The problem is that flattenLeft(xss) copies the first element list xss.head n 1 times, where n is the length of the list xss.

Note that both versions of flatten require a type annotation on the empty list that is the start value of the fold. This is due to a limitation in Scala’s type inferencer, which fails to infer the correct type of the list automatically. If you try to leave out the annotation, you get the following:

scala> def flattenRight[T](xss: List[List[T]]) = (xss :\ List()) (_ ::: _)

<console>:5: error: type mismatch; found : scala.List[T]

required: List[Nothing]

(xss :\ List()) (_ ::: _)

ˆ

To find out why the type inferencer goes wrong, you’ll need to know about the types of the fold methods and how they are implemented. More on this in Chapter 22.

Lastly, although the /: and :\ operators have the advantage that the direction of the slash resembles the graphical depiction of their respective left or right-leaning trees, and the associativity of the colon character places the start value in the same position in the expression as it is in the tree, some may find the resulting code less than intuitive. If you prefer, you can alternatively use the methods named foldLeft and foldRight, which are also defined on class List.

Example: List reversal using fold

Earlier in the chapter you saw an implementation of method reverse, named rev, whose running time was quadratic in the length of the list to be reversed. Here is now a different implementation of reverse that has linear cost. The idea is to use a fold left operation based on the following scheme:

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

def reverseLeft[T](xs: List[T]) = (startvalue /: xs)(operation)

It only remains to fill in the startvalue and operation parts. In fact, you can try to deduce these parts from some simple examples. To deduce the correct value of startvalue, you can start with the smallest possible list, List(), and calculate as follows:

List()

equals (by the properties of reverseLeft)

reverseLeft(List())

equals (by the template for reverseLeft)

(startvalue /: List())(operation) equals (by the definition of /:)

startvalue

Hence, startvalue must be List(). To deduce the second operand, you can pick the next smallest list as an example case. You know already that startvalue is List(), so you can calculate as follows:

List(x)

equals (by the properties of reverseLeft)

reverseLeft(List(x))

equals (by the template for reverseLeft, with startvalue = List())

(List() /: List(x)) (operation) equals (by the definition of /:)

operation(List(), x)

Hence, operation(List(), x) equals List(x), which can also be written as x :: List(). This suggests taking as operation the :: operator with its operands exchanged. (This operation is sometimes called “snoc,” in reference to ::, which is called cons.) We arrive then at the following implementation for reverseLeft:

def reverseLeft[T](xs: List[T]) = (List[T]() /: xs) {(ys, y) => y :: ys}

(Again, the type annotation in List[T]() is necessary to make the type inferencer work.) If you analyze the complexity of reverseLeft, you’ll

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