Scala Collections Series, Part 1 - Mutability and Lists

May 24, 2017

This blog post is the beginning of a three part series that will cover a variety of topics around Scala Collections, this part will cover:

Mutable and Immutable Collections
Lists
Traversable and Iterable
Sequence Traits (Seq, IndexedSeq, LinearSeq)

Mutable and Immutable Collections

Collections packaged in the Scala Collections library can have mutable and immutable variants, generally separated by package name. This can make switching between the two very straightforward, but may require aliasing them if you use immutable and mutable data structures in the same file.

For reference, here’s a diagram of the top level traits that are implemented in the mutable/immutable packages under scala.collection care of Scala’s documentation:

Scala Collections

The following packages provide concrete implementations for the above traits:

package scala.collection.immutable
package scala.collection.mutable

Lists

Here are some examples of their usage in the Scala REPL:

Welcome to Scala 2.11.11 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_131).
Type in expressions for evaluation. Or try :help.

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

scala> val mutableList = scala.collection.mutable.MutableList(1,2,3,4,5)
mutableList: scala.collection.mutable.MutableList[Int] = MutableList(1, 2, 3, 4, 5)

Notice how when we assign a list of Integers to aList, the REPL is able to report back that we now have a List[Int] available at aList. Also notice how when we create a MutableList, that type is reported back.

Let’s try a couple of operations on our lists:

scala> aList.map(x => x * 2)
res0: List[Int] = List(2, 4, 6, 8, 10)

scala> aList.filter(_ == 4)
res2: List[Int] = List(4)

scala> mutableList.map(x => x * 2)
res1: scala.collection.mutable.MutableList[Int] = MutableList(2, 4, 6, 8, 10)

scala> mutableList.filter(_ == 4)
res3: scala.collection.mutable.MutableList[Int] = MutableList(4)

When we apply operations map and filter to List and MutableList, we get back out Immutable or Mutable representations, respectively.

We can also stack operations as follows:

scala> aList.map(x => x * 16).filter(_ == 64)
res4: List[Int] = List(64)

In this case, we’ve created a new List of Integers (List[Int]) by applying map (multiplying each element by 16) then filtering to only include elements matching 64.

Traversable and Iterable

So now we’ve seen a how to create a simple immutable (and mutable) list, what’s under the hood of the immutable List (the MutableList examination will be left as an exercise to the reader :) ):

sealed abstract class List[+A]
  extends AbstractSeq[A]
  with LinearSeq[A]
  with Product
  with GenericTraversableTemplate[A, List]
  with LinearSeqOptimized[A, List[A]]
  with Serializable {

Yikes, that looks mildly terrifying, we’re mixing in a lot. Let’s take a look at only one of those, AbstractSeq[A]. The A let’s us know that the type of the list is A (be it an Int, a String, or otherwise).

Here’s the definition of AbstractSeq:

abstract class AbstractSeq[+A] extends AbstractIterable[A] with Seq[A]

The easy one is Seq. It provides a base trait for sequences, plus a few methods outside of the scope of this blog.

AbstractIterable[A] is pretty interesting. Keep in mind that everything in AbstractIterable[A] will be included in AbstractSeq. Here’s the definition:

abstract class AbstractIterable[+A] extends AbstractTraversable[A] with Iterable[A]

Oh great, now we’re mixing in an AbstractTraversable as well. We’ll cover that and Traversable in a minute, let’s first look at Iterable[A].

trait Iterable[+A]
  extends Traversable[A]
  with GenIterable[A]
  with GenericTraversableTemplate[A, Iterable]
  with IterableLike[A, Iterable[A]] {

Traversable[A] and Iterable[A] provide a considerable amount so (they actually inherit the functionality from Traversable and IterableLike, technically), let’s take a look at them separately:

Iterable

First, Iterable[A]’s more commonly used methods:

override def iterator: Iterator[A]
  - this creates a new iterator to iterate
    over all the elements contained in the iterable

override def takeRight(n: Int): Iterable[A]
  - this "takes" the last n elements
    in the iterable collection and returns them

override def dropRight(n: Int): Iterable[A]
  - this returns every element but the last n elements

Some examples:

scala> aList.iterator
res7: Iterator[Int] = non-empty iterator
scala> val aListIterator = aList.iterator
aListIterator: Iterator[Int] = non-empty iterator
scala> aListIterator.foreach { println(_) }
1
2
3
4
5
scala> aListIterator.foreach { println(_) }
scala> aList.takeRight(2)
res5: List[Int] = List(4, 5)
scala> aList.dropRight(2)
res6: List[Int] = List(1, 2, 3)

A note about why you don’t see anything after running foreach on the aListIterator: it’s exhausted it’s elements by the time the call is made again to foreach.

Traversable[A]’s more commonly used methods and example uses:

override def foreach[U](f: A => U): Unit
  - Applies the function f (which transforms the element of type A into an element of type U) to all elements of the collection and returns Unit
  scala> aList.foreach(print(_))
    12345

override def map[B, That](f: A => B): That
  - Applies the function f (which transforms the element of type A into an element of type U) to all elements of the collection and returns the transformed values in the form of a new collection
  scala> aList.map(x => x * 2)
  res16: List[Int] = List(2, 4, 6, 8, 10)

override def flatMap[B, That](f: A => GenTraversableOnce[B])
  - Applies flatten then the function f (which transforms the element of type A into an element of type U) to all elements of the collection and returns the transformed values in the form of a new collection
  scala> val makes = List("Ford", "Tesla", "Volkswagen")
  makes: List[String] = List(Ford, Tesla, Volkswagen)

  scala> makes.flatMap(_.toUpperCase)
  res20: List[Char] = List(F, O, R, D, T, E, S, L, A, V, O, L, K, S, W, A, G, E, N)

override def partition(p: A => Boolean)
  - Splits the collection into a tuple of two collections, with the left collection being those elements that satisfy the predicate, and the right collection being those elements that do not
  scala> aList.partition(_ > 2)
  res21: (List[Int], List[Int]) = (List(3, 4, 5),List(1, 2))

override def forall(p: A => Boolean): Boolean
  - Applies the predicate p to all elements in the collection and returns true if each element satisfies the predicate
  scala> aList.forall(_ < 10)
  res22: Boolean = true

override def exists(p: A => Boolean): Boolean
  - Applies the predicate p to all elements in the collection and returns true if the element exists in the collection
  scala> aList.exists(_ == 3)
  res23: Boolean = true

override def count(p: A => Boolean): Int
  - Applies the predicate p to all elements and returns the number of elements that match the predicate
  scala> aList.count(_ % 2 == 0)
  res24: Int = 2

override def find(p: A => Boolean): Option[A]
  - Applies the predicate p to all elements and returns the element if it exists in the collection
  scala> aList.find(_ == 2)
  res25: Option[Int] = Some(2)
  scala> aList.find(_ == 15)
  res26: Option[Int] = None

override def head: A
  - Returns the first element of the collection
  scala> aList.head
  res27: Int = 1

override def headOption: Option[A]
  - Returns the first element if the collection is non-empty, None if empty
  scala> aList.headOption
  res28: Option[Int] = Some(1)

  override def last: A
  scala> aList.last
  res29: Int = 5

override def mkString(sep: String): String
  - Makes a string using the provided separator
  scala> aList.mkString(",")
  res30: String = 1,2,3,4,5

override def sortWith(lt : (A,A) => Boolean): Traversable[A]
  - sort an array with a provided less than function
  scala> aList.sortWith((lhs,rhs) => lhs < rhs)
  res31: List[Int] = List(1, 2, 3, 4, 5)
  scala> aList.sortWith((lhs,rhs) => lhs > rhs)
  res32: List[Int] = List(5, 4, 3, 2, 1)

That about wraps up Iterable and Traversable, we’ll cover more of Traversable in later parts.

Sequence Traits (Seq, IndexedSeq, LinearSeq)

Seq

There’s a lot going on with Seq (and SeqLike). The commonly used methods include:

  def apply(idx: Int): A
  def contains[A1 >: A](elem: A1): Boolean
  def diff[B >: A](that: GenSeq[B]): Repr
  def length: Int
  def indexWhere(p: A => Boolean, from: Int): Int
  def intersect[B >: A](that: GenSeq[B])
  def lastIndexWhere(p: A => Boolean, end: Int): Int
  def reverse: Repr
  override def union[B >: A, That](that: GenSeq[B])

And less well known/used:

  def distinct
  def permutations: Iterator[Repr]
  def sortBy[B](f: A => B)(implicit ord: Ordering[B])
  def sortWith(lt: (A, A) => Boolean)
  def reverseMap[B, That](f: A => B)

I highly recommend reviewing them at:

SeqLike

IndexedSeq

This trait just implements iterator with apply and length. The code is pretty self-explanatory, and the IndexedSeqOptimized trait is worth exploring as well. See code for each here :

LinearSeq

this trait just implements iterator and corresponds with isEmpty, head, and tail. It’s also pretty self-explanatory, and the LinearSeqOptimized trait is worth a look. See code for each here (“Like” linked):