Code Examples for

Programming in Scala, Second Edition

Return to chapter index

24 The Scala Collections API

Sample run of chapter's interpreter examples

24.1 Mutable and immutable collections

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) = { | println("taking my time."); Thread.sleep(100) | 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.12 Performance characteristics

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) java.util.NoSuchElementException: key not found: 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]) = while (it.head.isEmpty) { it.next() }
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 scala> bit.head 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] scala> jul.add(7) java.lang.UnsupportedOperationException at java.util.AbstractList.add(AbstractList.java:131)

24.18 Migrating from Scala 2.7


>scala -deprecation -Xmigration Welcome to Scala version 2.8.1. Type in expressions to have them evaluated. Type :help for more information. 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)

24.19 Conclusion

For more information about Programming in Scala, Second Edition (the "Stairway Book"), please visit:

http://www.artima.com/shop/programming_in_scala_2ed

and:

http://booksites.artima.com/programming_in_scala_2ed

Copyright © 2007-2010 Artima, Inc. All rights reserved.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.