Programmation appliquée en Scala

Collections: recall List

Note: The content of units 13 and 14 is adapted from the slides of
"Functional Programming in Scala" by Prof. Martin Odersky.

A list having $x_1, ..., x_n$
as elements is written List( $x_1, …, x_n$ )

Example:

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

There are two important differences between lists and arrays.

Lists are immutable — the elements of a list cannot be changed.
Lists are recursive, while arrays are flat.

The figures below show the recursive structure of the fruit and diag3 lists.

Constructors of Lists

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.

For example:

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

Operations on Lists

All operations on lists can be expressed in terms of the following
three operations:

head : the first element of the list
tail : the list composed of all the elements except the first.
isEmpty : true if the list is empty, false otherwise.

These operations are defined as methods of objects of type list.

Example:

  fruit.head      == "apples"
  fruit.tail.head == "oranges"
  diag3.head      == List(1, 0, 0)
  empty.head      == throw new NoSuchElementException("head of empty list")

List Patterns

It is also 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`.
List(p1, ..., pn)	same as `p1 :: ... :: pn :: Nil`

Example:

`1 :: 2 :: xs`	Lists that start with `1` and then `2`
`x :: Nil`	Lists of length 1
`List(x)`	Same as `x :: Nil`
`List()`	The empty list, same as `Nil`
`List(2 :: xs)`	A list that contains as only element another list that starts with `2`.

Exercise

Consider the pattern x :: y :: List(xs, ys) :: zs.

What is the condition that describes most accurately the length L
of the lists it matches?

L == 3
L == 4
L == 5
L >= 3
L >= 4
L >= 5

List Methodes (1)

`xs.length`	The number of elements of `xs`
`xs.last`	The list's last element, exception if `xs` is empty
`xs.init`	A list consisting of all elements of `xs` except the last one, exception if `xs` is empty.
`xs take n`	A list consisting of the first `n` elements of `xs`, or `xs` itself if it is shorter than `n`.
`xs drop n`	The rest of the collection after taking `n` elements.
`xs(n)`	(or, written out, `xs` apply `n`). The element of `xs` at index `n`.

List Methodes (2)

Creating new lists

`xs ++ ys`	The list consisting of all elements of `xs` followed by all elements of `ys`.
`xs.reverse`	The list containing the elements of `xs` in reversed order
`xs updated (n, x)`	The list containing the same elements as `xs`, except at index `n` where it contains `x`

Finding elements

`xs indexOf x`	The index of the first element in `xs` equal to `x` or `-1` if `x` does not apear in `xs`.
`xs contains x`	same as `xs indexOf x >= 0`

Recurring Patterns for Computations on Lists

Functions on lists often have similar structures.

We can identify several recurring patterns, like,

transforming each element in a list in a certain way,
retrieving a list of all elements satisfying a criterion,
combining the elements of a list using an operator.

Functional languages allow programmers to write generic functions
that implement patterns such as these using higher-order functions.

Applying a Function to Elements of a List

A common operation is to transform each element of a list and then
return the list of results.

For example, to multiply each element of a list by the same factor, you could write:

  def scaleList(xs: List[Double], factor: Double): List[Double] = xs match {
    case Nil     => xs
    case y :: ys => y * factor :: scaleList(ys, factor)
  }

Map

This scheme can be generalized to the method map of the
List class. A simple way to define map is as follows:

  abstract class List[T] { ...
  def map[U](f: T => U): List[U] = this match {
    case Nil     => this
    case x :: xs => f(x) :: xs.map(f)
  }

(in fact, the actual definition of map is a bit different, also it works for arbitrary collections, not just lists).

Using map, scaleList can be written more concisely.

  def scaleList(xs: List[Double], factor: Double) =
    xs map (x => x * factor)

Exercise

Consider a function to square each element of a list, and
return the result. Complete the two following equivalent definitions of
squareList.

  def squareList(xs: List[Int]): List[Int] = xs match {
    case Nil     => ???
    case y :: ys => ???
  }

  def squareList(xs: List[Int]): List[Int] =
    xs map ???

Filtering

Another common operation on lists is the selection of all elements
satisfying a given condition. For example:

  def posElems(xs: List[Int]): List[Int] = xs match {
    case Nil     => xs
    case y :: ys => if (y > 0) y :: posElems(ys) else posElems(ys)
  }

Filter

This pattern is generalized by the method filter of the List class:

  abstract class List[T] {
    ...
    def filter(p: T => Boolean): List[T] = this match {
      case Nil     => this
      case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p)
    }
  }

Using filter, posElems can be written more concisely.

  def posElems(xs: List[Int]): List[Int] =
    xs filter (x => x > 0)

Variations of Filter

Besides filter, there are also the following methods that extract
sublists based on a predicate:

`xs filterNot p`	Same as `xs filter (x => !p(x))`; The list consisting of those elements of `xs` that do not satisfy the predicate `p`
`xs partition p`	Same as `(xs filter p, xs filterNot p)`, but computed in a single traversal of the list `xs`
`xs takeWhile p`	The longest prefix of list `xs` consisting of elements that all satisfy the predicate `p`.
`xs dropWhile p`	The remainder of the list `xs` after any leading elements satisfying `p have been removed.`
`xs span p`	Same as `(xs takeWhile p, xs dropWhile p)`but computed in a single traversal of the list `xs`

Exercise

Write a function pack that packs consecutive duplicates of list elements into sublists. For instance,

  pack(List("a", "a", "a", "b", "c", "c", "a"))

should give

  List(List("a", "a", "a"), List("b"), List("c", "c"), List("a")).

You can use the following template:

  def pack[T](xs: List[T]): List[List[T]] = xs match {
    case Nil      => Nil
    case x :: xs1 => ???
  }

Exercise

Using pack, write a function encode that produces the run-length
encoding of a list.

The idea is to encode n consecutive duplicates of an element x as a pair (x, n). For instance,

  encode(List("a", "a", "a", "b", "c", "c", "a"))

should give

  List(("a", 3), ("b", 1), ("c", 2), ("a", 1)).

Streams

A Stream is like a list except that its elements are computed lazily. Because of this, a stream can be infinitely long. Only those elements requested are computed. Otherwise, streams have the same performance characteristics as lists.

Whereas lists are constructed with the :: operator, streams are constructed with the similar-looking #::

Here is a simple example of a stream containing the integers 1, 2, and 3:

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

The head of this stream is 1, and the tail of it has 2 and 3. The tail is not printed here, though, because it hasn't been computed yet! Streams are specified to compute lazily.

Streams: example

Below is a more interesting example. It computes a stream that contains a Fibonacci sequence starting with the given two numbers.

A Fibonacci sequence is one where each element is the sum of the previous two elements in the series.

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

This function is deceptively simple:

The first element of the sequence is clearly a, and
the rest of the sequence is the Fibonacci sequence starting with b followed by a + b.

The tricky part is computing this sequence without causing an infinite recursion!

If the function used :: instead of #::, then every call to the function would result in another call, thus causing an infinite recursion. Since it uses #::, though, the right-hand side is not evaluated until it is requested.

Here are the first few elements of the Fibonacci sequence starting with two ones:

val fibs = fibFrom(1, 1).take(7)
//> fibs  : scala.collection.immutable.Stream[Int] = Stream(1, ?)
fibs.toList
//> res4: List[Int] = List(1, 1, 2, 3, 5, 8, 13)

Vectors

We have seen that lists are linear: Access to the first element is much faster than access to the middle or end of a list.

The Scala library also defines an alternative sequence implementation, Vector.

This one has more evenly balanced access patterns than List.

Operations on Vectors

Vectors are created analogously to lists:

  val nums = Vector(1, 2, 3, -88)
  val people = Vector("Bob", "James", "Peter")

They support the same operations as lists, with the exception of ::

Instead of x :: xs, there is

x +: xs Create a new vector with leading element x, followed by all elements of xs.

xs :+ x Create a new vector with trailing element x, preceded by all elements of xs.

(Note that the : always points to the sequence.)

Collection Hierarchy

A common base class of Vector, List and Stream is Seq, the class of all sequences.

Seq itself is a subclass of Iterable.

Arrays and Strings

Arrays and Strings support the same operations as Seq and can
implicitly be converted to sequences where needed.

(They cannot be subclasses of Seq because they come from Java)

  val xs: Array[Int] = Array(1, 2, 3)
  xs map (x => 2 * x)

  val ys: String = "Hello world!"
  ys filter (_.isUpper)

Ranges

Another simple kind of sequence is the range.

It represents a sequence of evenly spaced integers.

Three operators:

to (inclusive), until (exclusive), by (to determine step value):

  val r: Range = 1 until 5     //> r  : Range = Range(1, 2, 3, 4)
  val s: Range = 1 to 5     //> s  : Range = Range(1, 2, 3, 4, 5)
  1 to 10 by 3     //> res1: scala.collection.immutable.Range = Range(1, 4, 7, 10)
  6 to 1 by -2     //> res2: scala.collection.immutable.Range = Range(6, 4, 2)

Ranges are represented as single objects with three fields:
lower bound, upper bound, step value.

Some more Sequence Operations:

`xs exists p`	`true` if there is an element `x` of `xs` such that `p(x)` holds, `false` otherwise
`xs forall p`	`true` if `p(x)` holds for all elements `x` of `xs`,`false` otherwise.
`xs zip ys`	A sequence of pairs drawn from corresponding elements of sequences `xs` and `ys`.
`xs.unzip`	Splits a sequence of pairs `xs` into two sequences consisting of the first, respectively second halves of all pairs.
`xs.flatMap f`	Applies collection-valued function `f` to all elements of `xs` and concatenates the results.
`xs.sum`	The sum of all elements of this numeric collection
`xs.product`	The product of all elements of this numeric collection
`xs.max`	The maximum of all elements of this collection (an `ordering` must exist)
`xs.min`	The minimum of all elements of this collection

Example: Combinations

To list all combinations of numbers x and y where x is drawn from 1..M and y is drawn from 1..N:

  (1 to M) flatMap (x =>

Example: Combinations

To list all combinations of numbers x and y where x is drawn from 1..M and y is drawn from 1..N:

 (1 to M) flatMap (x => (1 to N) map (y => (x, y)))

Example: Scalar Product

To compute the scalar product of two vectors:

  def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
    (xs zip ys).map(xy => xy._1 * xy._2).sum

An alternative way to write this is with a pattern matching function value.

  def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
    (xs zip ys).map{ case (x, y) => x * y }.sum

Generally, the function value

  { case p1 => e1 ... case pn => en }

is equivalent to

  x => x match { case p1 => e1 ... case pn => en }

Exercise:

A number n is prime if the only divisors of n are 1 and n itself.

What is a high-level way to write a test for primality of numbers?
For once, value conciseness over efficiency.

  def isPrime(n: Int): Boolean = ???

Lab

Scary looking lab

You work with a buddy
One of you (the coder) writes the code, the other (the scribe) types up answers
When you get stuck, ask your buddy first!
Switch coder/scribe roles each lab
The coder submits the worksheet. Include the scribe's name in the worksheet!
The scribe submits answers. Include the coder's name in the report!

Operations on Collections

Write a function to drop every Nth element from a List. In your implementation first use the grouped methode to form groups of N elements.

drop(3, List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k')).toList
    //> res1: List[Char] = List(a, b, d, e, g, h, j, k)

Write a function to rotate a list N places to the left.

rotate(3, List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k'))
    //> res2: List[Char] = List(d, e, f, g, h, i, j, k, a, b, c)

Write a function to eliminate consecutive duplicates of list elements.

compress(List('a', 'a', 'a', 'b', 'b', 'c', 'a', 'a', 'd', 'd', 'e'))
    //> res3: List[Char] = List(a, b, c, a, d, e)

Write a function that inserts an element at a given position into a list.

insertAt('n', 2, List('a', 'b', 'c', 'd', 'e')) 
    //> res4: List[Char] = List(a, b, n, c, d, e)