Файл: Programming_in_Scala,_2nd_edition.pdf

yields the collection’s elements one by one. The foreach method from trait Traversable is implemented in Iterable in terms of iterator. Here is the actual implementation:

def foreach[U](f: Elem => U): Unit = { val it = iterator

while (it.hasNext) f(it.next())

}

Quite a few subclasses of Iterable override this standard implementation of foreach in Iterable, because they can provide a more efficient implementation. Remember that foreach is the basis of the implementation of all operations in Traversable, so its performance matters.

Two more methods exist in Iterable that return iterators: grouped and sliding. These iterators, however, do not return single elements but whole subsequences of elements of the original collection. The maximal size of these subsequences is given as an argument to these methods. The grouped method chunks its elements into increments, whereas sliding yields a sliding window over the elements. The difference between the two should become clear by looking at the following interpreter interaction:

scala> val xs = List(1, 2, 3, 4, 5) xs: List[Int] = List(1, 2, 3, 4, 5)

scala> val git = xs grouped 3

git: Iterator[List[Int]] = non-empty iterator

scala> git.next()

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

scala> git.next()

res3: List[Int] = List(4, 5)

scala> val sit = xs sliding 3

sit: Iterator[List[Int]] = non-empty iterator

scala> sit.next()

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

scala> sit.next()

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

scala> sit.next()

res6: List[Int] = List(3, 4, 5)

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

Trait Iterable also adds some other methods to Traversable that can be implemented efficiently only if an iterator is available. They are summarized in Table 24.2:

Table 24.2 · Operations in trait Iterable

Why have both Traversable and Iterable?

You might wonder why the extra trait Traversable is above Iterable. Can we not do everything with an iterator? So what’s the point of having

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

a more abstract trait that defines its methods in terms of foreach instead of iterator? One reason for having Traversable is that sometimes it is easier or more efficient to provide an implementation of foreach than to provide an implementation of iterator. Here’s a simple example. Let’s say you want a class hierarchy for binary trees that have integer elements at the leaves. You might design this hierarchy like this:

sealed abstract class Tree

case class Branch(left: Tree, right: Tree) extends Tree case class Node(elem: Int) extends Tree

Now assume you want to make trees traversable. To do this, have Tree inherit from Traversable[Int] and define a foreach method like this:

sealed abstract class Tree extends Traversable[Int] { def foreach[U](f: Int => U) = this match {

case Node(elem) => f(elem)

case Branch(l, r) => l foreach f; r foreach f

}

}

That’s not too hard, and it is also very efficient—traversing a balanced tree takes time proportional to the number of elements in the tree. To see this, consider that for a balanced tree with N leaves you will have N - 1 interior nodes of class Branch. So the total number of steps to traverse the tree is

N + N - 1.

Now, compare this with making trees iterable. To do this, have Tree inherit from Iterable[Int] and define an iterator method like this:

sealed abstract class Tree extends Iterable[Int] { def iterator: Iterator[Int] = this match {

case Node(elem) => Iterator.single(elem) case Branch(l, r) => l.iterator ++ r.iterator

}

}

At first glance, this looks no harder than the foreach solution. However, there’s an efficiency problem that has to do with the implementation of the iterator concatenation method, ++. Every time an element is produced by a

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

concatenated iterator such as l.iterator ++ r.iterator, the computation needs to follow one indirection to get at the right iterator (either l.iterator, or r.iterator). Overall, that makes log(N) indirections to get at a leaf of a balanced tree with N leaves. So the cost of visiting all elements of a tree went up from about 2N for the foreach traversal method to N log(N) for the traversal with iterator. If the tree has a million elements that means about two million steps for foreach and about twenty million steps for iterator. So the foreach solution has a clear advantage.

Subcategories of Iterable

In the inheritance hierarchy below Iterable you find three traits: Seq, Set, and Map. A common aspect of these three traits is that they all implement the

PartialFunction trait1 with its apply and isDefinedAt methods. However, the way each trait implements PartialFunction differs.

For sequences, apply is positional indexing, where elements are always numbered from 0. That is, Seq(1, 2, 3)(1) == 2. For sets, apply is a membership test. For instance, Set('a', 'b', 'c')('b') == true whereas Set()('a') == false. Finally for maps, apply is a selection. For instance,

Map('a' -> 1, 'b' -> 10, 'c' -> 100)('b') == 10.

In the following three sections, we will explain each of the three kinds of collections in more detail.

24.5 The sequence traits Seq, IndexedSeq, and

LinearSeq

The Seq trait represents sequences. A sequence is a kind of iterable that has a length and whose elements have fixed index positions, starting from 0.

The operations on sequences, summarized in Figure 24.3, fall into the following categories:

Indexing and length operations apply, isDefinedAt, length, indices, and lengthCompare. For a Seq, the apply operation means indexing; hence a sequence of type Seq[T] is a partial function that takes an Int argument (an index) and yields a sequence element of type T.

1Partial functions were described in Section 15.7.

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

In other words Seq[T] extends PartialFunction[Int, T]. The elements of a sequence are indexed from zero up to the length of the sequence minus one. The length method on sequences is an alias of the size method of general collections. The lengthCompare method allows you to compare the lengths of two sequences even if one of the sequences has infinite length.

Index search operations indexOf, lastIndexOf, indexOfSlice, lastIn- dexOfSlice, indexWhere, lastIndexWhere, segmentLength, and prefixLength, which return the index of an element equal to a given value or matching some predicate.

Addition operations +:, :+, and padTo, which return new sequences obtained by adding elements at the front or the end of a sequence.

Update operations updated and patch, which return a new sequence obtained by replacing some elements of the original sequence.

Sorting operations sorted, sortWith, and sortBy, which sort sequence elements according to various criteria.

Reversal operations reverse, reverseIterator, and reverseMap, which yield or process sequence elements in reverse order, from last to first.

Comparison operations startsWith, endsWith, contains, corresponds, and containsSlice, which relate two sequences or search an element in a sequence.

Multiset operations intersect, diff, union, and distinct, which perform set-like operations on the elements of two sequences or remove duplicates.

If a sequence is mutable, it offers in addition a side-effecting update method, which lets sequence elements be updated. Recall from Chapter 3 that syntax like seq(idx) = elem is just a shorthand for seq.update(idx, elem). Note the difference between update and updated. The update method changes a sequence element in place, and is only available for mutable sequences. The updated method is available for all sequences and always returns a new sequence instead of modifying the original.

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

Table 24.3 · Operations in trait Seq

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