Файл: Programming_in_Scala,_2nd_edition.pdf

Table 24.11 treats mutable and immutable sets and maps with the following operations:

24.14Equality

The collection libraries have a uniform approach to equality and hashing. The idea is, first, to divide collections into sets, maps, and sequences. Collections in different categories are always unequal. For instance, Set(1, 2, 3) is unequal to List(1, 2, 3) even though they contain the same elements. On the other hand, within the same category, collections are equal if and

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

Table 24.10 · Performance characteristics of sequence types

Table 24.11 · Performance characteristics of set and map types

aAssuming bits are densely packed.

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

only if they have the same elements (for sequences: the same elements in the same order). For example, List(1, 2, 3) == Vector(1, 2, 3), and

HashSet(1, 2) == TreeSet(2, 1).

It does not matter for the equality check whether a collection is mutable or immutable. For a mutable collection, equality simply depends on the current elements at the time the equality test is performed. This means that a mutable collection might be equal to different collections at different times, depending what elements are added or removed. This is a potential trap when using a mutable collection as a key in a hash map. For example:

scala> import collection.mutable.{HashMap, ArrayBuffer} import collection.mutable.{HashMap, ArrayBuffer}

scala> val buf = ArrayBuffer(1, 2, 3)

buf: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(1, 2, 3)

scala> val map = HashMap(buf -> 3)

map: scala.collection.mutable.HashMap[scala.collection. mutable.ArrayBuffer[Int],Int] = Map((ArrayBuffer(1, 2, 3),3))

scala> map(buf) res13: Int = 3

scala> buf(0) += 1

scala> map(buf) java.util.NoSuchElementException: key not found:

ArrayBuffer(2, 2, 3)

In this example, the selection in the last line will most likely fail because the hash code of the array xs has changed in the second-to-last line. Therefore, the hash-code-based lookup will look at a different place than the one in which xs was stored.

24.15Views

Collections have quite a few methods that construct new collections. Some examples are map, filter, and ++. We call such methods transformers because they take at least one collection as their receiver object and produce another collection in their result.

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

Transformers can be implemented in two principal ways: strict and nonstrict (or lazy). A strict transformer constructs a new collection with all of its elements. A non-strict, or lazy, transformer constructs only a proxy for the result collection, and its elements are constructed on demand.

As an example of a non-strict transformer, consider the following implementation of a lazy map operation:

def lazyMap[T, U](coll: Iterable[T], f: T => U) = new Iterable[U] {

def iterator = coll.iterator map f

}

Note that lazyMap constructs a new Iterable without stepping through all elements of the given collection coll. The given function f is instead applied to the elements of the new collection’s iterator as they are demanded.

Scala collections are by default strict in all their transformers, except for Stream, which implements all its transformer methods lazily. However, there is a systematic way to turn every collection into a lazy one and vice versa, which is based on collection views. A view is a special kind of collection that represents some base collection, but implements all of its transformers lazily.

To go from a collection to its view, you can use the view method on the collection. If xs is some collection, then xs.view is the same collection, but with all transformers implemented lazily. To get back from a view to a strict collection, you can use the force method.

As an example, say you have a vector of Ints over which you want to map two functions in succession:

scala> val v = Vector(1 to 10: _*)

v: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> v map (_ + 1) map (_ * 2)

res5: scala.collection.immutable.Vector[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

In the last statement, the expression v map (_ + 1) constructs a new vector that is then transformed into a third vector by the second call to map (_ * 2). In many situations, constructing the intermediate result from the first call to map is a bit wasteful. In the pseudo example, it would be faster to do a

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

single map with the composition of the two functions (_ + 1) and (_ * 2). If you have the two functions available in the same place you can do this by hand. But quite often, successive transformations of a data structure are done in different program modules. Fusing those transformations would then undermine modularity. A more general way to avoid the intermediate results is by turning the vector first into a view, applying all transformations to the view, and finally forcing the view to a vector:

scala> (v.view map (_ + 1) map (_ * 2)).force

res12: Seq[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

We’ll do this sequence of operations again, one by one:

scala> val vv = v.view

vv: scala.collection.SeqView[Int,Vector[Int]] = SeqView(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

The application v.view gives you a SeqView, i.e., a lazily evaluated Seq. The type SeqView has two type parameters. The first, Int, shows the type of the view’s elements. The second, Vector[Int], shows you the type constructor you get back when forcing the view.

Applying the first map to the view gives you:

scala> vv map (_ + 1)

res13: scala.collection.SeqView[Int,Seq[_]] = SeqViewM(...)

The result of the map is a value that prints SeqViewM(...). This is in essence a wrapper that records the fact that a map with function (_ + 1) needs to be applied on the vector v. It does not apply that map until the view is forced, however. The “M” after SeqView is an indication that the view encapsulates a map operation. Other letters indicate other delayed operations. For instance “S” indicates a delayed slice operation, and “R” indicates a reverse. We’ll now apply the second map to the last result.

scala> res13 map (_ * 2)

res14: scala.collection.SeqView[Int,Seq[_]] = SeqViewMM(...)

You now get a SeqView that contains two map operations, so it prints with a double “M”: SeqViewMM(...). Finally, forcing the last result gives:

scala> res14.force

res15: Seq[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

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