## 24 The Scala Collections API

Sample run of chapter's interpreter examples

### 24.2 Collections consistency

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

List(1, 2, 3)
HashMap("x" -> 24, "y" -> 25, "z" -> 26)

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)

```

### 24.3 Trait Traversable

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

```

### 24.4 Trait Iterable

```
def foreach[U](f: Elem => U): Unit = {
val it = iterator
while (it.hasNext) f(it.next())
}

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)

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

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

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

```

### 24.5 Sets

```
scala> val fruit = Set("apple", "orange", "peach", "banana")
fruit: scala.collection.immutable.Set[java.lang.String] =
Set(apple, orange, peach, banana)

scala> fruit("peach")
res7: Boolean = true

scala> fruit("potato")
res8: Boolean = false

scala> var s = Set(1, 2, 3)
s: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

scala> s += 4; s -= 2

scala> s
res9: scala.collection.immutable.Set[Int] = Set(1, 3, 4)

scala> val s = collection.mutable.Set(1, 2, 3)
s: scala.collection.mutable.Set[Int] = Set(1, 2, 3)

scala> s += 4
res10: s.type = Set(1, 4, 2, 3)

scala> s -= 2
res11: s.type = Set(1, 4, 3)

scala> val myOrdering = Ordering.fromLessThan[String](_ > _)
myOrdering: scala.math.Ordering[String] = ...

scala> import scala.collection.immutable.TreeSet
import scala.collection.immutable.TreeSet

scala> TreeSet.empty(myOrdering)
res12: scala.collection.immutable.TreeSet[String] = TreeSet()

scala> val set = TreeSet.empty[String]
set: scala.collection.immutable.TreeSet[String] = TreeSet()

scala> val numbers = set + ("one", "two", "three", "four")
numbers: scala.collection.immutable.TreeSet[String] =
TreeSet(four, one, three, two)

scala> numbers range ("one", "two")
res13: scala.collection.immutable.TreeSet[String]
= TreeSet(one, three)

scala> numbers from "three"
res14: scala.collection.immutable.TreeSet[String]
= TreeSet(three, two)

```

### 24.6 Maps

```
def get(key): Option[Value]

scala> def f(x: String) = {
| x.reverse }
f: (x: String)String

scala> val cache = collection.mutable.Map[String, String]()
cache: scala.collection.mutable.Map[String,String] = Map()

scala> def cachedF(s: String) = cache.getOrElseUpdate(s, f(s))
cachedF: (s: String)String

scala> cachedF("abc")
taking my time.
res15: String = cba

scala> cachedF("abc")
res16: String = cba

def cachedF(arg: String) = cache get arg match {
case Some(result) => result
case None =>
val result = f(arg)
cache(arg) = result
result
}

```

### 24.7 Synchronized sets and maps

```
import scala.collection.mutable.{Map,
SynchronizedMap, HashMap}

object MapMaker {

def makeMap: Map[String, String] = {

new HashMap[String, String] with
SynchronizedMap[String, String] {

override def default(key: String) =
"Why do you want to know?"
}
}
}

new HashMap[String, String] with
SynchronizedMap[String, String]

override def default(key: String) =
"Why do you want to know?"

scala> val capital = MapMaker.makeMap
capital: scala.collection.mutable.Map[String,String] = Map()

scala> capital ++= List("US" -> "Washington",
|      "France" -> "Paris", "Japan" -> "Tokyo")
res17: scala.collection.mutable.Map[String,String] =
Map((France,Paris), (US,Washington), (Japan,Tokyo))

scala> capital("Japan")
res18: String = Tokyo

scala> capital("New Zealand")
res19: String = Why do you want to know?

scala> capital += ("New Zealand" -> "Wellington")
res20: capital.type = Map((New Zealand,Wellington),...

scala> capital("New Zealand")
res21: String = Wellington

// In file collections/Misc.scala

import scala.collection.mutable

val synchroSet =
new mutable.HashSet[Int] with
mutable.SynchronizedSet[Int]

```

### 24.8 Concrete immutable collection classes

```
scala> val str = 1 #:: 2 #:: 3 #:: Stream.empty
str: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> def fibFrom(a: Int, b: Int): Stream[Int] =
|   a #:: fibFrom(b, a + b)
fibFrom: (a: Int,b: Int)Stream[Int]

scala> val fibs = fibFrom(1, 1).take(7)
fibs: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> fibs.toList
res22: List[Int] = List(1, 1, 2, 3, 5, 8, 13)

scala> val vec = scala.collection.immutable.Vector.empty
vec: scala.collection.immutable.Vector[Nothing] = Vector()

scala> val vec2 = vec :+ 1 :+ 2
vec2: scala.collection.immutable.Vector[Int] = Vector(1, 2)

scala> val vec3 = 100 +: vec2
vec3: scala.collection.immutable.Vector[Int]
= Vector(100, 1, 2)

scala> vec3(0)
res23: Int = 100

scala> val vec = Vector(1, 2, 3)
vec: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)

scala> vec updated (2, 4)
res24: scala.collection.immutable.Vector[Int] = Vector(1, 2, 4)

scala> vec
res25: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)

scala> collection.immutable.IndexedSeq(1, 2, 3)
res26: scala.collection.immutable.IndexedSeq[Int]
= Vector(1, 2, 3)

scala> val stack = scala.collection.immutable.Stack.empty
stack: scala.collection.immutable.Stack[Nothing] = Stack()

scala> val hasOne = stack.push(1)
hasOne: scala.collection.immutable.Stack[Int] = Stack(1)

scala> stack
res27: scala.collection.immutable.Stack[Nothing] = Stack()

scala> hasOne.top
res28: Int = 1

scala> hasOne.pop
res29: scala.collection.immutable.Stack[Int] = Stack()

scala> val empty = scala.collection.immutable.Queue[Int]()
empty: scala.collection.immutable.Queue[Int] = Queue()

scala> val has1 = empty.enqueue(1)
has1: scala.collection.immutable.Queue[Int] = Queue(1)

scala> val has123 = has1.enqueue(List(2, 3))
has123: scala.collection.immutable.Queue[Int]
= Queue(1, 2, 3)

scala> val (element, has23) = has123.dequeue
element: Int = 1
has23: scala.collection.immutable.Queue[Int] = Queue(2, 3)

scala> 1 to 3
res30: scala.collection.immutable.Range.Inclusive
with scala.collection.immutable.Range.ByOne
= Range(1, 2, 3)

scala> 5 to 14 by 3
res31: scala.collection.immutable.Range
= Range(5, 8, 11, 14)

scala> 1 until 3
res32: scala.collection.immutable.Range
with scala.collection.immutable.Range.ByOne = Range(1, 2)

scala> val set = collection.immutable.TreeSet.empty[Int]
set: scala.collection.immutable.TreeSet[Int] = TreeSet()

scala> set + 1 + 3 + 3
res33: scala.collection.immutable.TreeSet[Int]
= TreeSet(1, 3)

scala> val bits = scala.collection.immutable.BitSet.empty
bits: scala.collection.immutable.BitSet = BitSet()

scala> val moreBits = bits + 3 + 4 + 4
moreBits: scala.collection.immutable.BitSet = BitSet(3, 4)

scala> moreBits(3)
res34: Boolean = true

scala> moreBits(0)
res35: Boolean = false

scala> val map = collection.immutable.ListMap(
1 -> "one", 2 -> "two")
map: scala.collection.immutable.ListMap[Int,java.lang.String]
= Map((1,one), (2,two))

scala> map(2)
res36: java.lang.String = two

```

### 24.9 Concrete mutable collection classes

```
scala> val buf = collection.mutable.ArrayBuffer.empty[Int]
buf: scala.collection.mutable.ArrayBuffer[Int]
= ArrayBuffer()

scala> buf += 1
res37: buf.type = ArrayBuffer(1)

scala> buf += 10
res38: buf.type = ArrayBuffer(1, 10)

scala> buf.toArray
res39: Array[Int] = Array(1, 10)

scala> val buf = collection.mutable.ListBuffer.empty[Int]
buf: scala.collection.mutable.ListBuffer[Int]
= ListBuffer()

scala> buf += 1
res40: buf.type = ListBuffer(1)

scala> buf += 10
res41: buf.type = ListBuffer(1, 10)

scala> buf.toList
res42: List[Int] = List(1, 10)

scala> val buf = new StringBuilder
buf: StringBuilder = StringBuilder()

scala> buf += 'a'
res43: buf.type = StringBuilder(a)

scala> buf ++= "bcdef"
res44: buf.type = StringBuilder(a, b, c, d, e, f)

scala> buf.toString
res45: String = abcdef

scala> val queue = new scala.collection.mutable.Queue[String]
queue: scala.collection.mutable.Queue[String] = Queue()

scala> queue += "a"
res46: queue.type = Queue(a)

scala> queue ++= List("b", "c")
res47: queue.type = Queue(a, b, c)

scala> queue
res48: scala.collection.mutable.Queue[String] = Queue(a, b, c)

scala> queue.dequeue
res49: String = a

scala> queue
res50: scala.collection.mutable.Queue[String] = Queue(b, c)

scala> val stack = new scala.collection.mutable.Stack[Int]
stack: scala.collection.mutable.Stack[Int] = Stack()

scala> stack.push(1)
res51: stack.type = Stack(1)

scala> stack
res52: scala.collection.mutable.Stack[Int] = Stack(1)

scala> stack.push(2)
res53: stack.type = Stack(2, 1)

scala> stack
res54: scala.collection.mutable.Stack[Int] = Stack(2, 1)

scala> stack.top
res55: Int = 2

scala> stack
res56: scala.collection.mutable.Stack[Int] = Stack(2, 1)

scala> stack.pop
res57: Int = 2

scala> stack
res58: scala.collection.mutable.Stack[Int] = Stack(1)

scala> val map = collection.mutable.HashMap.empty[Int,String]
map: scala.collection.mutable.HashMap[Int,String] = Map()

scala> map += (1 -> "make a web site")
res59: map.type = Map((1,make a web site))

scala> map += (3 -> "profit!")
res60: map.type = Map((1,make a web site), (3,profit!))

scala> map(1)
res61: String = make a web site

scala> map contains 2
res62: Boolean = false

scala> val bits = scala.collection.mutable.BitSet.empty
bits: scala.collection.mutable.BitSet = BitSet()

scala> bits += 1
res63: bits.type = BitSet(1)

scala> bits += 3
res64: bits.type = BitSet(1, 3)

scala> bits
res65: scala.collection.mutable.BitSet = BitSet(1, 3)

```

### 24.10 Arrays

```
scala> val a1 = Array(1, 2, 3)
a1: Array[Int] = Array(1, 2, 3)

scala> val a2 = a1 map (_ * 3)
a2: Array[Int] = Array(3, 6, 9)

scala> val a3 = a2 filter (_ % 2 != 0)
a3: Array[Int] = Array(3, 9)

scala> a3.reverse
res1: Array[Int] = Array(9, 3)

scala> val seq: Seq[Int] = a1
seq: Seq[Int] = WrappedArray(1, 2, 3)

scala> val a4: Array[Int] = seq.toArray
a4: Array[Int] = Array(1, 2, 3)

scala> a1 eq a4
res2: Boolean = true

scala> val seq: Seq[Int] = a1
seq: Seq[Int] = WrappedArray(1, 2, 3)

scala> seq.reverse
res2: Seq[Int] = WrappedArray(3, 2, 1)

scala> val ops: collection.mutable.ArrayOps[Int] = a1
ops: scala.collection.mutable.ArrayOps[Int] = [I(1, 2, 3)

scala> ops.reverse
res3: Array[Int] = Array(3, 2, 1)

scala> a1.reverse
res4: Array[Int] = Array(3, 2, 1)

scala> intArrayOps(a1).reverse
res5: Array[Int] = Array(3, 2, 1)

// This is wrong!
def evenElems[T](xs: Vector[T]): Array[T] = {
val arr = new Array[T]((xs.length + 1) / 2)
for (i <- 0 until xs.length by 2)
arr(i / 2) = xs(i)
arr
}

error: cannot find class manifest for element type T
val arr = new Array[T]((arr.length + 1) / 2)
^

def evenElems[T](xs: Vector[T])
(implicit m: ClassManifest[T]): Array[T] = ...

// This works
def evenElems[T: ClassManifest](xs: Vector[T]): Array[T] = {
val arr = new Array[T]((xs.length + 1) / 2)
for (i <- 0 until xs.length by 2)
arr(i / 2) = xs(i)
arr
}

scala> evenElems(Vector(1, 2, 3, 4, 5))
res6: Array[Int] = Array(1, 3, 5)

scala> evenElems(Vector("this", "is", "a", "test", "run"))
res7: Array[java.lang.String] = Array(this, a, run)

scala> def wrap[U](xs: Vector[U]) = evenElems(xs)
<console>:6: error: could not find implicit value for
evidence parameter of type ClassManifest[U]
def wrap[U](xs: Vector[U]) = evenElems(xs)
^

scala> def wrap[U: ClassManifest](xs: Vector[U]) =
evenElems(xs)
wrap: [U](xs: Vector[U])(implicit evidence\$1:
ClassManifest[U])Array[U]

```

### 24.11 Strings

```
scala> val str = "hello"
str: java.lang.String = hello

scala> str.reverse
res6: String = olleh

scala> str.map(_.toUpper)
res7: String = HELLO

scala> str drop 3
res8: String = lo

scala> str slice (1, 4)
res9: String = ell

scala> val s: Seq[Char] = str
s: Seq[Char] = WrappedString(h, e, l, l, o)

```

### 24.13 Equality

```
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)
ArrayBuffer(2, 2, 3)

```

### 24.14 Views

```
def lazyMap[T, U](coll: Iterable[T], f: T => U) =
new Iterable[U] {
def iterator = coll.iterator map f
}

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)

scala> (v.view map (_ + 1) map (_ * 2)).force
res12: Seq[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

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

scala> vv map (_ + 1)
res13: scala.collection.SeqView[Int,Seq[_]] = SeqViewM(...)

scala> res13 map (_ * 2)
res14: scala.collection.SeqView[Int,Seq[_]] = SeqViewMM(...)

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

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

findPalindrome(words take 1000000)

findPalindrome(words.view take 1000000)

scala> val arr = (0 to 9).toArray
arr: Array[Int] = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> val subarr = arr.view.slice(3, 6)
subarr: scala.collection.mutable.IndexedSeqView[
Int,Array[Int]] = IndexedSeqViewS(...)

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

scala> negate(subarr)

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

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

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

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

```

### 24.15 Iterators

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

it foreach println

for (elem <- it) println(elem)

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

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

val (it1, it2) = it.duplicate

// This won't work
def skipEmptyWordsNOT(it: Iterator[String]) {
while (it.next().isEmpty) {}
}

def skipEmptyWords(it: BufferedIterator[String]) =

scala> val it = Iterator(1, 2, 3, 4)
it: Iterator[Int] = non-empty iterator

scala> val bit = it.buffered
bit: java.lang.Object with scala.collection.
BufferedIterator[Int] = non-empty iterator

res10: Int = 1

scala> bit.next()
res11: Int = 1

scala> bit.next()
res11: Int = 2

```

### 24.16 Creating collections from scratch

```
Traversable()             // An empty traversable object
List()                    // The empty list
List(1.0, 2.0)            // A list with elements 1.0, 2.0
Vector(1.0, 2.0)          // A vector with elements 1.0, 2.0
Iterator(1, 2, 3)         // An iterator returning three integers.
Set(dog, cat, bird)       // A set of three animals
HashSet(dog, cat, bird)   // A hash set of the same animals
Map('a' -> 7, 'b' -> 0)   // A map from characters to integers

List.apply(1.0, 2.0)

scala> List(1, 2, 3)
res17: List[Int] = List(1, 2, 3)

scala> Traversable(1, 2, 3)
res18: Traversable[Int] = List(1, 2, 3)

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

```

### 24.17 Conversions between Java and Scala collections

```
Iterator         \Leftrightarrow    java.util.Iterator
Iterator         \Leftrightarrow    java.util.Enumeration
Iterable         \Leftrightarrow    java.lang.Iterable
Iterable         \Leftrightarrow    java.util.Collection
mutable.Buffer   \Leftrightarrow    java.util.List
mutable.Set      \Leftrightarrow    java.util.Set
mutable.Map      \Leftrightarrow    java.util.Map

scala> import collection.JavaConversions._
import collection.JavaConversions._

scala> import collection.mutable._
import collection.mutable._

scala> val jul: java.util.List[Int] = ArrayBuffer(1, 2, 3)
jul: java.util.List[Int] = [1, 2, 3]

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

scala> val m: java.util.Map[String, Int] =
HashMap("abc" -> 1, "hello" -> 2)
m: java.util.Map[String,Int] = {hello=2, abc=1}

Seq          \Rightarrow   java.util.List
mutable.Seq  \Rightarrow   java.util.List
Set          \Rightarrow   java.util.Set
Map          \Rightarrow   java.util.Map

scala> val jul: java.util.List[Int] = List(1, 2, 3)
jul: java.util.List[Int] = [1, 2, 3]

java.lang.UnsupportedOperationException

```

### 24.18 Migrating from Scala 2.7

```
>scala -deprecation -Xmigration
Welcome to Scala version 2.8.1.
Type in expressions to have them evaluated.

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

scala> List.unzip(xs)
<console>:7: warning: method unzip in object List is
deprecated: use xs.unzip instead of List.unzip(xs)
List.unzip(xs)
^
res0: (List[Int], List[Int]) = (List(1, 3),List(2, 4))

scala> xs.unzip
res1: (List[Int], List[Int]) = (List(1, 3),List(2, 4))

scala> val m = xs.toMap
m: scala.collection.immutable.Map[Int,Int] = Map((1,2), (3,4))

scala> m.keys
<console>:8: warning: method keys in trait MapLike has
changed semantics: As of 2.8, keys returns Iterable[A]
rather than Iterator[A].
m.keys
^
res2: Iterable[Int] = Set(1, 3)

```