Scala Tutorial

Standard Library

View on GitHub

List

The list is a fundamental data structure in functional programming.

A list having x1, …, xn as elements is written List(x1, …, xn):

val fruit = List("apples", "oranges", "pears")
val nums = List(1, 2, 3, 4)
val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty = List()

Lists are immutable --- the elements of a list cannot be changed,
Lists are recursive (as you will see in the next subsection),
Lists are homogeneous: A list is intended to be composed of elements that all have the same type.

That's because when you create a List of elements with different types it will look for a common ancestor. The common ancestor for all types is Any

val heterogeneousList: List[Any] = List(1, "1", '1')

The type of a list with elements of type T is written List[T]:

val fruit: List[String] = List("apples", "oranges", "pears")
val nums: List[Int] = List(1, 2, 3, 4)
val diag3: List[List[Int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty: List[Nothing] = List()

Constructors of Lists

Actually, all lists are constructed from:

the empty list Nil, and
the construction operation :: (pronounced cons): x :: xs gives a new list with the first element x, followed by the elements of xs (which is a list itself).

For example:

val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
val nums = 1 :: (2 :: (3 :: (4 :: Nil)))
val empty = Nil

Right Associativity

Convention: Operators ending in “:” associate to the right.

A :: B :: C is interpreted as A :: (B :: C).

We can thus omit the parentheses in the definition above.

val nums = 1 :: 2 :: 3 :: 4 :: Nil

Operators ending in “:” are also different in the fact that they are seen as method calls of the right-hand operand.

So the expression above is equivalent to:

val nums = Nil.::(4).::(3).::(2).::(1)

Manipulating Lists

It is possible to decompose lists with pattern matching:

Nil: the Nil constant,
p :: ps: A pattern that matches a list with a head matching p and a tail matching ps.

nums match {
  // Lists of `Int` that starts with `1` and then `2`
  case 1 :: 2 :: xs => …
  // Lists of length 1
  case x :: Nil => …
  // Same as `x :: Nil`
  case List(x) => …
  // The empty list, same as `Nil`
  case List() =>
  // A list that contains as only element another list that starts with `2`
  case List(2 :: xs) => …
}

Exercise: Sorting Lists

Suppose we want to sort a list of numbers in ascending order:

One way to sort the list List(7, 3, 9, 2) is to sort the tail List(3, 9, 2) to obtain List(2, 3, 9).
The next step is to insert the head 7 in the right place to obtain the result List(2, 3, 7, 9).

This idea describes Insertion Sort:

def insertionSort(xs: List[Int]): List[Int] = xs match {
  case List() => List()
  case y :: ys => insert(y, insertionSort(ys))
}

Complete the definition insertion sort by filling in the blanks in the definition below:

val cond: (Int, Int) => Boolean = res0
def insert(x: Int, xs: List[Int]): List[Int] =
  xs match {
    case List() => x :: res1
    case y :: ys =>
      if (cond(x, y)) x :: y :: ys
      else y :: insert(x, ys)
  }
insert(2, 1 :: 3 :: Nil) shouldBe (1 :: 2 :: 3 :: Nil)
insert(1, 2 :: 3 :: Nil) shouldBe (1 :: 2 :: 3 :: Nil)
insert(3, 1 :: 2 :: Nil) shouldBe (1 :: 2 :: 3 :: Nil)

Common Operations on Lists

Transform the elements of a list using map:

List(1, 2, 3).map(x => x + 1) == List(2, 3, 4)

Filter elements using filter:

List(1, 2, 3).filter(x => x % 2 == 0) == List(2)

Transform each element of a list into a list and flatten the results into a single list using flatMap:

val xs =
  List(1, 2, 3).flatMap { x =>
    List(x, 2 * x, 3 * x)
  }
xs == List(1, 2, 3, 2, 4, 6, 3, 6, 9)

Optional Values

We represent an optional value of type A with the type Option[A]. This is useful to implement, for instance, partially defined functions:

// The `sqrt` function is not defined for negative values
def sqrt(x: Double): Option[Double] = …

An Option[A] can either be None (if there is no value) or Some[A] (if there is a value):

def sqrt(x: Double): Option[Double] =
  if (x < 0) None else Some(…)

Manipulating Options

It is possible to decompose options with pattern matching:

def foo(x: Double): String =
  sqrt(x) match {
    case None => "no result"
    case Some(y) => y.toString
  }

Common Operations on Options

Transform an optional value with map:

Some(1).map(x => x + 1) shouldBe Some(2)
None.map((x: Int) => x + 1) shouldBe None
res0.map(x => x + 1) shouldBe res1

Filter values with filter:

Some(1).filter(x => x % 2 == 0) shouldBe None
Some(2).filter(x => x % 2 == 0) shouldBe Some(2)
res0.filter(x => x % 2 == 0) shouldBe res1

Use flatMap to transform a successful value into an optional value:

Some(1).flatMap(x => Some(x + 1)) shouldBe Some(2)
None.flatMap((x: Int) => Some(x + 1)) shouldBe None
res0.flatMap(x => Some(x + 1)) shouldBe res1

Error Handling

This subsection introduces types that are useful to handle failures.

Try

Try[A] represents a computation that attempted to return an A. It can either be:

a Success[A],
or a Failure.

The key difference between None and Failures is that the latter provide the reason for the failure:

def sqrt(x: Double): Try[Double] =
  if (x < 0) Failure(new IllegalArgumentException("x must be positive"))
  else Success(…)

Manipulating `Try[A]` values

Like options and lists, Try[A] is an algebraic data type, so it can be decomposed using pattern matching.

Try[A] also have map, filter and flatMap. They behave the same as with Option[A], except that any exception that is thrown during their execution is converted into a Failure.

Either

Either can also be useful to handle failures. Basically, the type Either[A, B] represents a value that can either be of type A or of type B. It can be decomposed in two cases: Left or Right.

You can use one case to represent the failure and the other to represent the success. What makes it different from Try is that you can choose a type other than Throwable to represent the exception. Another difference is that exceptions that occur when transforming Either values are not converted into failures.

def sqrt(x: Double): Either[String, Double] =
  if (x < 0) Left("x must be positive")
  else Right(…)

Manipulating `Either[A, B]` Values

Since Scala 2.12, Either has map and flatMap. These methods transform the Right case only. We say that Either is “right biased”:

Right(1).map((x: Int) => x + 1) shouldBe Right(2)
Left("foo").map((x: Int) => x + 1) shouldBe Left("foo")

Either also has a filterOrElse method that turns a Right value into a Left value if it does not satisfy a given predicate:

Right(1).filterOrElse(x => x % 2 == 0, "Odd value") shouldBe Left("Odd value")

However, prior to Scala 2.12, Either was “unbiased”. You had to explicitly specify which “side” (Left or Right) you wanted to map:

def triple(x: Int): Int = 3 * x

def tripleEither(x: Either[String, Int]): Either[String, Int] =
  x.map(triple)

tripleEither(Right(1)) shouldBe res0
tripleEither(Left("not a number")) shouldBe res1