Файл: Programming_in_Scala,_2nd_edition.pdf

Both stored functions get applied as part of the execution of the force operation and a new vector is constructed. That way, no intermediate data structure is needed.

One detail to note is that the static type of the final result is a Seq, not a Vector. Tracing the types back we see that as soon as the first delayed map was applied, the result had static type SeqViewM[Int, Seq[_]]. That is, the “knowledge” that the view was applied to the specific sequence type Vector got lost. The implementation of a view for any particular class requires quite a bit of code, so the Scala collection libraries provide views mostly only for general collection types, not for specific implementations.6

There are two reasons why you might want to consider using views. The first is performance. You have seen that by switching a collection to a view the construction of intermediate results can be avoided. These savings can be quite important. As another example, consider the problem of finding the first palindrome in a list of words. A palindrome is a word that reads backwards the same as forwards. Here are the necessary definitions:

def isPalindrome(x: String) = x == x.reverse

def findPalindrome(s: Seq[String]) = s find isPalindrome

Now, assume you have a very long sequence words and you want to find a palindrome in the first million words of that sequence. Can you re-use the definition of findPalindrome? Of course, you could write:

findPalindrome(words take 1000000)

This nicely separates the two aspects of taking the first million words of a sequence and finding a palindrome in it. But the downside is that it always constructs an intermediary sequence consisting of one million words, even if the first word of that sequence is already a palindrome. So potentially, 999,999 words are copied into the intermediary result without being inspected at all afterwards. Many programmers would give up here and write their own specialized version of finding palindromes in some given prefix of an argument sequence. But with views, you don’t have to. Simply write:

findPalindrome(words.view take 1000000)

6An exception to this is arrays: applying delayed operations on arrays will again give results with static type Array.

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

This has the same nice separation of concerns, but instead of a sequence of a million elements it will only construct a single lightweight view object. This way, you do not need to choose between performance and modularity.

The second use case applies to views over mutable sequences. Many transformer functions on such views provide a window into the original sequence that can then be used to update selectively some elements of that sequence. To see this in an example, suppose you have an array arr:

scala> val arr = (0 to 9).toArray

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

You can create a subwindow into that array by creating a slice of a view of the array:

scala> val subarr = arr.view.slice(3, 6)

subarr: scala.collection.mutable.IndexedSeqView[ Int,Array[Int]] = IndexedSeqViewS(...)

This gives a view, subarr, which refers to the elements at positions 3 through 5 of the array arr. The view does not copy these elements, it just provides a reference to them. Now, assume you have a method that modifies some elements of a sequence. For instance, the following negate method would negate all elements of the sequence of integers it’s given:

scala> def negate(xs: collection.mutable.Seq[Int]) = for (i <- 0 until xs.length) xs(i) = -xs(i)

negate: (xs: scala.collection.mutable.Seq[Int])Unit

Assume now you want to negate elements at positions three through five of the array arr. Can you use negate for this? Using a view, this is simple:

scala> negate(subarr)

scala> arr

res4: Array[Int] = Array(0, 1, 2, -3, -4, -5, 6, 7, 8, 9)

What happened here is that negate changed all elements of subarr, which were a slice of the elements of arr. Again, you see that views help in keeping things modular. The code above nicely separated the question of what index range to apply a method to from the question what method to apply.

After having seen all these nifty uses of views you might wonder why have strict collections at all? One reason is that performance comparisons do

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

not always favor lazy over strict collections. For smaller collection sizes the added overhead of forming and applying closures in views is often greater than the gain from avoiding the intermediary data structures. A possibly more important reason is that evaluation in views can be very confusing if the delayed operations have side effects.

Here’s an example that bit a few users of versions of Scala before 2.8. In these versions the Range type was lazy, so it behaved in effect like a view. People were trying to create a number of actors7 like this:

val actors = for (i <- 1 to 10) yield actor { ... }

They were surprised that none of the actors were executing afterwards, even though the actor method should create and start an actor from the code that’s enclosed in the braces following it. To explain why nothing happened, remember that the for expression above is equivalent to an application of the map method:

val actors = (1 to 10) map (i => actor { ... })

Since previously the range produced by (1 to 10) behaved like a view, the result of the map was again a view. That is, no element was computed, and, consequently, no actor was created! Actors would have been created by forcing the range of the whole expression, but it’s far from obvious that this is what was required to make the actors do their work.

To avoid surprises like this, the Scala 2.8 collections library has more regular rules. All collections except streams and views are strict. The only way to go from a strict to a lazy collection is via the view method. The only way to go back is via force. So the actors definition above would behave as expected in Scala 2.8 in that it would create and start ten actors. To get back the surprising previous behavior, you’d have to add an explicit view method call:

val actors = for (i <- (1 to 10).view) yield actor { ... }

In summary, views are a powerful tool to reconcile concerns of efficiency with concerns of modularity. But in order not to be entangled in aspects of delayed evaluation, you should restrict views to two scenarios. Either you apply views in purely functional code where collection transformations do

7An actor is a thread that can communicate with message passing; see Chapter 32.

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

not have side effects. Or you apply them over mutable collections where all modifications are done explicitly. What’s best avoided is a mixture of views and operations that create new collections while also having side effects.

24.16Iterators

An iterator is not a collection, but rather a way to access the elements of a collection one by one. The two basic operations on an iterator it are next and hasNext. A call to it.next() will return the next element of the iterator and advance the state of the iterator. Calling next again on the same iterator will then yield the element one beyond the one returned previously. If there are no more elements to return, a call to next will throw a NoSuchElementException. You can find out whether there are more elements to return using Iterator’s hasNext method.

The most straightforward way to “step through” all the elements returned by an iterator is to use a while loop:

while (it.hasNext) println(it.next())

Iterators in Scala also provide analogues of most of the methods that you find in the Traversable, Iterable, and Seq traits. For instance, they provide a foreach method that executes a given procedure on each element returned by an iterator. Using foreach, the loop above could be abbreviated to:

it foreach println

As always, for expressions can be used as an alternate syntax for expressions involving foreach, map, filter, and flatMap, so yet another way to print all elements returned by an iterator would be:

for (elem <- it) println(elem)

There’s an important difference between the foreach method on iterators and the same method on traversable collections: When called on an iterator, foreach will leave the iterator at its end when it is done. So calling next again on the same iterator will fail with a NoSuchElementException. By contrast, when called on a collection, foreach leaves the number of elements in the collection unchanged (unless the passed function adds or re-

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

moves elements, but this is discouraged, because it can easily lead to surprising results).

The other operations that Iterator has in common with Traversable have the same property of leaving the iterator at its end when done. For instance, iterators provide a map method, which returns a new iterator:

scala> val it = Iterator("a", "number", "of", "words") it: Iterator[java.lang.String] = non-empty iterator

scala> it.map(_.length)

res1: Iterator[Int] = non-empty iterator

scala> res1 foreach println 1 6 2 5

scala> it.next()

java.util.NoSuchElementException: next on empty iterator

As you can see, after the call to map, the it iterator has advanced to its end. Another example is the dropWhile method, which can be used to find the first element of an iterator that has a certain property. For instance, to find the first word in the iterator shown previously that has at least two characters,

you could write:

scala> val it = Iterator("a", "number", "of", "words") it: Iterator[java.lang.String] = non-empty iterator

scala> it dropWhile (_.length < 2)

res4: Iterator[java.lang.String] = non-empty iterator

scala> it.next()

res5: java.lang.String = number

Note again that it has changed by the call to dropWhile: it now points to the second word “number” in the list. In fact, it and the result res4 returned by dropWhile will return exactly the same sequence of elements.

There is only one standard operation, duplicate, which allows you to re-use the same iterator:

val (it1, it2) = it.duplicate

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

The call to duplicate gives you two iterators, which each return exactly the same elements as the iterator it. The two iterators work independently; advancing one does not affect the other. By contrast the original iterator, it, is advanced to its end by duplicate and is thus rendered unusable.

In summary, iterators behave like collections if you never access an iterator again after invoking a method on it. The Scala collection libraries make this explicit with an abstraction called TraversableOnce, which is a common supertrait of Traversable and Iterator. As the name implies, TraversableOnce objects can be traversed using foreach, but the state of that object after the traversal is not specified. If the TraversableOnce object is in fact an Iterator, it will be at its end after the traversal, but if it is a Traversable, it will still exist as before. A common use case of TraversableOnce is as an argument type for methods that can take either an iterator or traversable as argument. An example is the appending method ++ in trait Traversable. It takes a TraversableOnce parameter, so you can append elements coming from either an iterator or a traversable collection.

All operations on iterators are summarized in Table 24.12:

Table 24.12 · Operations in trait Iterator

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

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