Odersky M. Programming in Scala

Подождите немного. Документ загружается.

Section 23.4 Chapter 23 · For Expressions Revisited 511

for (x <- expr

; y = expr

; seq) yield expr

Assume again that seq is a (possibly empty) sequence of generators, deﬁni-

tions, and ﬁlters. This expression is translated to the following one:

for ((x, y) <- for (x <- expr

) yield (x, expr

); seq)

yield expr

So you see that expr

is evaluated each time there is a new x value being

generated. This re-evaluation is necessary, because expr

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 deﬁ-

nitions 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

it’s usually better to write:

val y = expensiveComputationNotInvolvingX

for (x <- 1 to 1000) yield x

Translating for loops

The previous subsections showed how for expressions that contain a yield

are translated. What about for loops that simply perform a side effect with-

out 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

) body

translates to:

expr

foreach (x => body)

A larger example is the expression:

for (x <- expr

; if expr

; y <- expr

) body

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

Section 23.5 Chapter 23 · For Expressions Revisited 512

This expression translates to:

expr

filter (x => expr

) foreach (x =>

expr

foreach (y => body))

For example, the following expression sums up all elements of a matrix rep-

resented as a list of lists:

var sum = 0

for (xs <- xss; x <- xs) sum += x

This loop is translated into two nested foreach applications:

var sum = 0

xss foreach (xs =>

xs foreach (x =>

sum += x))

23.5 Going the other way

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 im-

plementations of the three methods in terms of for expressions. The meth-

ods 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)

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

}

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

Section 23.6 Chapter 23 · For Expressions Revisited 513

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.

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.

23.6 Generalizing for

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, deﬁne operations map, flatMap,

and filter. Because they deﬁne 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 implementa-

tions of sets. It’s also perfectly possible for your own data types to support

for expressions by deﬁning the necessary methods. To support the full range

of for expressions and for loops, you need to deﬁne map, flatMap, filter,

and foreach as methods of your data type. But it’s also possible to deﬁne

a subset of these methods, and thereby support a subset of all possible for

expressions or loops. Here are the precise rules:

• If your type deﬁnes just map, it allows for expressions consisting of a

single generator.

• If it deﬁnes flatMap as well as map, it allows for expressions consist-

ing of several generators.

• If it deﬁnes foreach, it allows for loops (both with single and multi-

ple generators).

• If it deﬁnes filter, it allows for ﬁlter expressions starting with an if

in the for expression.

The translation of for expressions happens before type checking. This al-

lows for maximal ﬂexibility, because it is only required that the result of

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

Section 23.6 Chapter 23 · For Expressions Revisited 514

expanding a for expression type checks. Scala deﬁnes no typing rules for

the for expressions themselves, and does not require map, flatMap, filter,

or foreach to have any particular type signatures.

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 ﬁrst 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, rang-

ing from collections, to computations with state and I/O, backtracking com-

putations, 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 hav-

ing 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. There-

fore, 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,

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

Section 23.7 Chapter 23 · For Expressions Revisited 515

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.

23.7 Conclusion

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 expres-

sions are really much more general than mere iterations over collections, and

that you can design your own classes to support them.

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

Chapter 24

Extractors

By now you have probably grown accustomed to the concise way data can be

decomposed and analyzed using pattern matching. This chapter shows you

how to generalize this concept further. Until now, constructor patterns were

linked to case classes. For instance, Some(x) is a valid pattern because Some

is a case class. Sometimes you might wish that you could write patterns like

this without creating an associated case class. In fact, you might wish to be

able to create your own kinds of patterns. Extractors give you a way to do

so. This chapter explains what extractors are and how you can use them to

deﬁne patterns that are decoupled from an object’s representation.

24.1 An example: Extracting email addresses

To illustrate the problem extractors solve, imagine that you need to analyze

strings that represent email addresses. Given a string, you want to decide

whether it is an email address or not, and, if it is, you want to access the user

and domain parts of the address. The traditional way to do this uses three

helper functions:

def isEMail(s: String): Boolean

def domain(s: String): String

def user(s: String): String

With these functions, you could parse a given string s as follows:

if (isEMail(s)) println(user(s) +" AT "+ domain(s)

else println("not an email address")

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

Section 24.2 Chapter 24 · Extractors 517

This works, but is kind of clumsy. What’s more, things would become more

complicated if you combined several such tests. For instance you might want

to ﬁnd two successive strings in a list that are both email addresses with

the same user. You can try this yourself with the access functions deﬁned

previously to see what would be involved.

You saw already in Chapter 15 that pattern matching is ideal for attacking

problems like this. Let’s assume for the moment that you could match a

string with a pattern:

EMail(user, domain)

The pattern would match if the string contained an embedded at sign (@). In

that case it would bind variable user to the part of the string before the @

and variable domain to the part after it. Postulating a pattern like this, the

previous expression could be written more clearly like this:

s match {

case EMail(user, domain) => println(user +" AT "+ domain)

case _ => println("not an email address")

}

The more complicated problem of ﬁnding two successive email addresses

with the same user part would translate to the following pattern:

ss match {

case EMail(u1, d1) :: EMail(u2, d2) :: _ if (u1 == u2) => ...

...

}

This is much more legible than anything that could be written with access

functions. However, the problem is that strings are not case classes; they do

not have a representation that conforms to EMail(user, domain). This is

where Scala’s extractors come in: they let you deﬁne new patterns for pre-

existing types, where the pattern need not follow the internal representation

of the type.

24.2 Extractors

An extractor in Scala is an object that has a method called unapply as one of

its members. The purpose of that unapply method is to match a value and

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

Section 24.2 Chapter 24 · Extractors 518

take it apart. Often, the extractor object also deﬁnes a dual method apply for

building values, but this is not required. As an example, Listing 24.1 shows

an extractor object for email addresses:

object EMail {

// The injection method (optional)

def apply(user: String, domain: String) = user +"@"+ domain

// The extraction method (mandatory)

def unapply(str: String): Option[(String, String)] = {

val parts = str split "@"

if (parts.length == 2) Some(parts(0), parts(1)) else None

}

Listing 24.1 · The EMail string extractor object.

This object deﬁnes both apply and unapply methods. The apply method

has the same meaning as always: it turns EMail into an object that can

be applied to arguments in parentheses in the same way a method is ap-

plied. So you can write EMail("John", "epfl.ch") to construct the string

"John@epfl.ch". To make this more explicit, you could also let EMail

inherit from Scala’s function type, like this:

object EMail extends (String, String) => String { ... }

Note

The “(String, String) => String” portion of the previous object

declaration means the same as Function2[String, String, String],

which declares an abstract apply method that EMail implements. As a

result of this declaration, you could, for example, pass EMail to a method

expecting a Function2[String, String, String].

The unapply method is what turns EMail into an extractor. In a sense, it

reverses the construction process of apply. Where apply takes two strings

and forms an email address string out of them, unapply takes an email ad-

dress and returns potentially two strings: the user and the domain of the ad-

dress. But unapply must also handle the case where the given string is not

an email address. That’s why unapply returns an Option-type over pairs of

strings. Its result is either Some(user, domain) if the string str is an email

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

Section 24.2 Chapter 24 · Extractors 519

address with the given user and domain parts,

or None, if str is not an

email address. Here are some examples:

unapply("John@epfl.ch") equals Some("John", "epfl.ch")

unapply("John Doe") equals None

Now, whenever pattern matching encounters a pattern referring to an extrac-

tor object, it invokes the extractor’s unapply method on the selector expres-

sion. For instance, executing the code:

selectorString match { case EMail(user, domain) => ... }

would lead to the call:

EMail.unapply(selectorString)

As you saw previously, this call to EMail.unapply will return either None

or Some(u, d), for some values u for the user part of the address and d

for the domain part. In the None case, the pattern does not match, and the

system tries another pattern or fails with a MatchError exception. In the

Some(u, d) case, the pattern matches and its variables are bound to the ele-

ments of the returned value. In the previous match, user would be bound to

u and domain would be bound to d.

In the EMail pattern matching example, the type String of the selec-

tor expression, selectorString, conformed to unapply’s argument type

(which in the example was also String). This is quite common, but not

necessary. It would also be possible to use the EMail extractor to match se-

lector expressions for more general types. For instance, to ﬁnd out whether

an arbitrary value x was an email address string, you could write:

val x: Any = ...

x match { case EMail(user, domain) => ... }

Given this code, the pattern matcher will ﬁrst check whether the given value

x conforms to String, the parameter type of EMail’s unapply method. If it

does conform, the value is cast to String and pattern matching proceeds as

before. If it does not conform, the pattern fails immediately.

As demonstrated here, where Some is applied to the tuple, (user, domain), you can

leave off one pair of parentheses when passing a tuple to a function that takes a single argu-

ment. Thus, Some(user, domain) means the same as Some((user, domain)).

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

Section 24.3 Chapter 24 · Extractors 520

In object EMail, the apply method is called an injection, because it takes

some arguments and yields an element of a given set (in our case: the set of

strings that are email addresses). The unapply method is called an extrac-

tion, because it takes an element of the same set and extracts some of its parts

(in our case: the user and domain substrings). Injections and extractions are

often grouped together in one object, because then you can use the object’s

name for both a constructor and a pattern, which simulates the convention

for pattern matching with case classes. However, it is also possible to deﬁne

an extraction in an object without a corresponding injection. The object itself

is called an extractor, independently of whether it has an apply method or

not.

If an injection method is included, it should be the dual to the extraction

method. For instance, a call of:

EMail.unapply(EMail.apply(user, domain))

should return:

Some(user, domain)

i.e., the same sequence of arguments wrapped in a Some. Going in the other

direction means running ﬁrst the unapply and then the apply, as shown in

the following code:

EMail.unapply(obj) match {

case Some(u, d) => EMail.apply(u, d)

}

In that code, if the match on obj succeeds, you’d expect to get back that

same object from the apply. These two conditions for the duality of apply

and unapply are good design principles. They are not enforced by Scala,

but it’s recommended to keep to them when designing your extractors.

24.3 Patterns with zero or one variables

The unapply method of the previous example returned a pair of element

values in the success case. This is easily generalized to patterns of more than

two variables. To bind N variables, an unapply would return an N-element

tuple, wrapped in a Some.

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