Файл: Programming_in_Scala,_2nd_edition.pdf

elements of a collection as a side effect. Immutable collections, by contrast, never change. You still have operations that simulate additions, removals, or updates, but those operations will in each case return a new collection and leave the old collection unchanged.

All collection classes are found in the package scala.collection or one of its subpackages: mutable, immutable, and generic. Most collection classes needed by client code exist in three variants, each of which has different characteristics with respect to mutability. The three variants are located in packages scala.collection, scala.collection.immutable, and scala.collection.mutable.

A collection in package scala.collection.immutable is guaranteed to be immutable for everyone. Such a collection will never change after it is created. Therefore, you can rely on the fact that accessing the same collection value repeatedly at different points in time will always yield a collection with the same elements.

A collection in package scala.collection.mutable is known to have some operations that change the collection in place. These operations let you write code to mutate the collection yourself. However, you must be careful to understand and defend against any updates performed by other parts of the code base.

A collection in package scala.collection can be either mutable or immutable. For instance, scala.collection.IndexedSeq[T] is a supertrait of both scala.collection.immutable.IndexedSeq[T] and its mutable sibling scala.collection.mutable.IndexedSeq[T]. Generally, the root collections in package scala.collection define the same interface as the immutable collections. And typically, the mutable collections in package scala.collection.mutable add some side-effecting modification operations to this immutable interface.

The difference between root collections and immutable collections is that clients of an immutable collection have a guarantee that nobody can mutate the collection, whereas clients of a root collection only know that they can’t change the collection themselves. Even though the static type of such a collection provides no operations for modifying the collection, it might still be possible that the run-time type is a mutable collection that can be changed by other clients.

By default, Scala always picks immutable collections. For instance, if you just write Set without any prefix or without having imported anything, you get an immutable set, and if you write Iterable you get an immutable

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

iterable, because these are the default bindings imported from the scala package. To get the mutable default versions, you need to write explicitly collection.mutable.Set, or collection.mutable.Iterable.

The last package in the collection hierarchy is collection.generic. This package contains building blocks for implementing collections. Typically, collection classes defer the implementations of some of their operations to classes in generic. Everyday users of the collection framework on the other hand should need to refer to classes in generic only in exceptional circumstances.

24.2 Collections consistency

The most important collection classes are shown in Figure 24.1. There is quite a bit of commonality shared by all these classes. For instance, every kind of collection can be created by the same uniform syntax, writing the collection class name followed by its elements:

Traversable(1, 2, 3)

Iterable("x", "y", "z")

Map("x" -> 24, "y" -> 25, "z" -> 26)

Set(Color.Red, Color.Green, Color.Blue)

SortedSet("hello", "world")

Buffer(x, y, z)

IndexedSeq(1.0, 2.0)

LinearSeq(a, b, c)

The same principle also applies for specific collection implementations:

List(1, 2, 3)

HashMap("x" -> 24, "y" -> 25, "z" -> 26)

The toString methods for all collections produce output written as above, with a type name followed by the elements of the collection in parentheses. All collections support the API provided by Traversable, but their methods all return their own class rather than the root class Traversable. For instance, the map method on List has a return type of List, whereas the map method on Set has a return type of Set. Thus the static return type of these methods is fairly precise:

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

Traversable

Iterable

Seq

IndexedSeq

Vector

ResizableArray

GenericArray

LinearSeq

MutableList

List

Stream

Buffer

ListBuffer

ArrayBuffer

Set

SortedSet

TreeSet

HashSet (mutable)

LinkedHashSet

HashSet (immutable)

BitSet

EmptySet, Set1, Set2, Set3, Set4

Map

SortedMap

TreeMap

HashMap (mutable)

LinkedHashMap (mutable)

HashMap (immutable)

EmptyMap, Map1, Map2, Map3, Map4

Figure 24.1 · Collection hierarchy.

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

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

scala> Set(1, 2, 3) map (_ * 2)

res1: scala.collection.immutable.Set[Int] = Set(2, 4, 6)

Equality is also organized uniformly for all collection classes; more on this in Section 24.14.

Most of the classes in Figure 24.1 exist in three variants: root, mutable, and immutable. The only exception is the Buffer trait, which only exists as a mutable collection.

In the remainder of this chapter, we will review these classes one by one.

24.3 Trait Traversable

At the top of the collection hierarchy is trait Traversable. Its only abstract operation is foreach:

def foreach[U](f: Elem => U)

Collection classes implementing Traversable just need to define this method; all other methods can be inherited from Traversable.

The foreach method is meant to traverse all elements of the collection, and apply the given operation, f, to each element. The type of the operation is Elem => U, where Elem is the type of the collection’s elements and U is an arbitrary result type. The invocation of f is done for its side effect only; in fact any function result of f is discarded by foreach.

Traversable also defines many concrete methods, which are all listed in Table 24.1 on page 539. These methods fall into the following categories:

Addition ++, which appends two traversables together, or appends all elements of an iterator to a traversable.

Map operations map, flatMap, and collect, which produce a new collection by applying some function to collection elements.

Conversions toIndexedSeq, toIterable, toStream, toArray, toList, toSeq, toSet, and toMap, which turn a Traversable collection into a more specific collection. All these conversions return the receiver object if it already matches the demanded collection type. For instance, applying toList to a list will yield the list itself.

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

Copying operations copyToBuffer and copyToArray. As their names imply, these copy collection elements to a buffer or array, respectively.

Size operations isEmpty, nonEmpty, size, and hasDefiniteSize. Collections that are traversable can be finite or infinite. An example of an infinite traversable collection is the stream of natural numbers

Stream.from(0). The method hasDefiniteSize indicates whether a collection is possibly infinite. If hasDefiniteSize returns true, the collection is certainly finite. If it returns false, the collection might be infinite, in which case size will emit an error or not return.

Element retrieval operations head, last, headOption, lastOption, and find. These select the first or last element of a collection, or else the first element matching a condition. Note, however, that not all collections have a well-defined meaning of what “first” and “last” means. For instance, a hash set might store elements according to their hash keys, which might change from run to run. In that case, the “first” element of a hash set could also be different for different runs of a program. A collection is ordered if it always yields its elements in the same order. Most collections are ordered, but some (such as hash sets) are not—dropping the ordering provides a little bit of extra efficiency. Ordering is often essential to give reproducible tests and help in debugging. That’s why Scala collections provide ordered alternatives for all collection types. For instance, the ordered alternative for HashSet is LinkedHashSet.

Subcollection retrieval operations takeWhile, tail, init, slice, take, drop, filter, dropWhile, filterNot, and withFilter. These all return some subcollection identified by an index range or a predicate.

Subdivision operations splitAt, span, partition, and groupBy, which split the elements of this collection into several subcollections.

Element tests exists, forall, and count, which test collection elements with a given predicate.

Folds foldLeft, foldRight, /:, :\, reduceLeft, reduceRight, which apply a binary operation to successive elements.

Specific folds sum, product, min, and max, which work on collections of specific types (numeric or comparable).

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