Collections in Scala

Collections are of great significance in programming. Our decision on how to store a collection of elements determines the efficiency of our programs. Scala includes an elegant and powerful collection library, which we will dive into right now!

Mutable & Immutable

• Mutable collections: can be changed after created
• Immutable collections: cannot be changed after created

Trait Traversable

The only abstract operation is foreach,

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

• The invocation of f is done for its side effect only; any function result of f is discarded by foreach.

Trait Iterable

All methods in this trait are defined in terms of an abstract method, iterator.

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

• Two more methods exist in Iterable that return iterators: grouped and sliding.

Why have both Traversable and Iterable?

Because The method foreach is more efficient to implement than the method iterator!

Three traits

• Seq
• Set
• Map

Concrete collection classes:

| immutable: Lists (finite), Streams (computed lazily, thus can be infinite), Vectors (access to any lements of a vector take only “effectively constant time”), Stacks (rarely used, is subsumed by lists), Queues, Ranges (to, until, by), Hash tries (the default implementation of maps and sets), Red-black trees (used by TreeSet and TreeMap), bit sets, List maps.

| mutable: Array buffers (appending an item to an array buffer takes amortized constant time), List buffers, String builders, Linked lists, doubled linked lists, lists (a single linked list + a pointer refers to the terminal empty node → fast appending), queues, array sequences (store elements internally in an Array[AnyRef]), stacks, hash tables (the default implementation of maps and sets), bit sets.

Array

Scala arrays correspond one-to-one to Java arrays, but:

1. They can be generic

• Scala compiler maps Array[T] to the type Array[AnyRef].
• At run-time, when an element of an array of type Array[T] is accessed or updated there are some type tests that determine the actual array type — slow down array operations by a factor of 3–4.
• Use ClassTag when creating an array at runtime.

2. They are compatible with Scala sequences — Implicit conversions!

WrappedArray & ArrayOps:

WrappedArray: long-lived, lower priority

ArrayOps: short-lives, higher priority

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

Equality

1. Divide collections into sets, maps, and sequences. Collections in different categories are always unequal.
2. Second, within the same category, collections are equal i.f.f. they have the same elements (no matter whether immutable or not).

Views

Def: A View is a special kind of collection that represents some base collection, but implements all of its transformers lazily.

• By default, only streams and views are non-strict (lazy).
• .view → from a strict to a lazy collection; .force → from a lazy to a strict collection

Iterators

• An iterator is not a collection, but rather a way to access the element of a collection one by one.
• Also provide a foreach method.
• Difference between the foreach method on iterators and the same method on traversable collections: When called on an iterator, foreach will leave the iterator at its end when it’s done.

val it = Iterator("a", "number", "of", "words")
val res = it.map(_.length)
res foreach println // 1 6 2 5
it.next() // NoSuchElementException

Thus, iterators behave like collections if you never access an iterator again after invoking a method on it.

BufferedIterator:

• an extra method, head, to return the first element, but not advance the iterator.
• Conversion: it.buffered