Sequences

A sequence is one of the fundamental abstractions in high-level programming. In particular, a sequence is a collection of objects that have been grouped together in a designated order. In Scala, sequence objects implement the trait Seq.

Let us do a small workout with sequences at the Scala console. (Open up a console so that you can play with the examples as we go!)

An Array object in Scala is an example of a sequence. Let us create a small array of integers at the console:

scala> val a = Array(752, 884, 995, 462, 126, 632, 445)
a: Array[Int] = Array(752, 884, 995, 462, 126, 632, 445)

Note

A key property of sequences is that every object in a sequence has an index (or position) by which it can be addressed. The first object in the sequence has index 0, the second object has index 1, and so forth.

We can readily verify this at the console:

scala> a(0)
res: Int = 752

scala> a(1)
res: Int = 884

scala> a(6)
res: Int = 445

Each sequence object has a number of methods that enable us to get information and manipulate the sequence to our convenience. For example, the length of a sequence is the number of objects in it:

scala> a.length
res: Int = 7

Fundamental to a sequence is that we can use and manipulate the order in which the elements are positioned in the sequence. For example, the reverse method of a sequence returns a new sequence with the same objects but in reverse order:

scala> a
res: Array[Int] = Array(752, 884, 995, 462, 126, 632, 445)

scala> a.reverse
res: Array[Int] = Array(445, 632, 126, 462, 995, 884, 752)

Similarly, we can obtain new sequences from an existing sequence by taking and dropping elements from the existing sequence, or by slicing a contiguous segment starting and ending at a specified position:

scala> a
res: Array[Int] = Array(752, 884, 995, 462, 126, 632, 445)

scala> a.take(3)
res: Array[Int] = Array(752, 884, 995)

scala> a.drop(2)
res: Array[Int] = Array(995, 462, 126, 632, 445)

scala> a.takeRight(2)
res: Array[Int] = Array(632, 445)

scala> a.dropRight(3)
res: Array[Int] = Array(752, 884, 995, 462)

scala> a.slice(1,3)
res: Array[Int] = Array(884, 995)

You are invited to study the documentation of trait Seq to pick up further useful methods.

Certain sequences are useful enough that they have their own shorthand functions by which they can be created. A particularly useful case are ranges of consecutive integers:

scala> Range(0,10)
res: scala.collection.immutable.Range.Exclusive = Range 0 until 10

scala> Range(10,20)
res: scala.collection.immutable.Range.Exclusive = Range 10 until 20

Representing the integer sequences \(0,1,2,...9\) and \(10, 11, ...19\) respectively. Note that the Range is exclusive (meaning the upper bound of the range is excluded).

A sequence (such as a Range) can be converted to an array by the method .toArray if needed:

scala> Range(10,20).toArray
val res: Array[Int] = Array(10, 11, 12, 13, 14, 15, 16, 17, 18, 19)

Transforming sequences

A great many tasks in programming require us to transform a sequence of objects into another sequence in some controlled way.

Mapping. Perhaps the most common such transformation is that we apply a function to each element in the sequence. This transformation is often called mapping the function across the sequence.

To show an example of mapping, let us define a simple function that squares a given integer:

scala> def square(x: Int) = x*x
def square(x: Int): Int

scala> square(5)
res: Int = 25

We can now map the function across a sequence to obtain a sequence consisting of the square of each element in the original sequence:

scala> a
res: Array[Int] = Array(752, 884, 995, 462, 126, 632, 445)

scala> a.map(square)
res: Array[Int] = Array(565504, 781456, 990025, 213444, 15876, 399424, 198025)

Mapping and anonymous functions. Mapping is particularly convenient when used together with anonymous functions, which we can give directly as an argument to map without introducing a separate named function:

scala> a.map((x: Int) => x*x)
res: Array[Int] = Array(565504, 781456, 990025, 213444, 15876, 399424, 198025)

Furthermore, we can in many cases omit the type specifications because Scala can automatically infer the types for us:

scala> a.map(x => x*x)
res: Array[Int] = Array(565504, 781456, 990025, 213444, 15876, 399424, 198025)

Filtering using a predicate. Another very common transformation is that we must select all elements that satisfy some specific property from a sequence. This transformation is often called filtering the sequence for the elements of interest.

We define the elements that we want using a function that takes as argument an element and returns true if the element is interesting, and false otherwise. Such a function is often called a predicate.

For example, suppose we want to filter a sequence for all of its even elements. Let us define a predicate that indicates whether an integer is even:

scala> def isEven(x: Int) = x%2 == 0
def isEven(x: Int): Boolean

scala> isEven(0)
res: Boolean = true

scala> isEven(1)
res: Boolean = false

scala> isEven(2)
res: Boolean = true

scala> isEven(3)
res: Boolean = false

We can now use the predicate to filter a sequence for its even elements:

scala> a
res: Array[Int] = Array(752, 884, 995, 462, 126, 632, 445)

scala> a.filter(isEven)
res: Array[Int] = Array(752, 884, 462, 126, 632)

Again we can use anonymous functions if we so want:

scala> a.filter(x => x % 2 == 0)
res: Array[Int] = Array(752, 884, 462, 126, 632)

scala> a.filter(_ % 2 == 0)
res: Array[Int] = Array(752, 884, 462, 126, 632)

Reducing and folding. Often it is necessary to summarise the elements of a sequence by applying a two-argument associative function across the elements of the sequence. This operation is called reducing the sequence.

A common example is that we want to take the sum of the elements of the sequence:

scala> def myPlus(left: Int, right: Int) = left+right
def myPlus(left: Int, right: Int): Int

scala> a.reduce(myPlus)
res: Int = 4296

Again we may use anonymous functions:

scala> a.reduce((left: Int, right: Int) => left+right)
res: Int = 4296

scala> a.reduce((left, right) => left+right)
res: Int = 4296

scala> a.reduce(_ + _)
res: Int = 4296

Sums are in fact important enough that they are available also as a dedicated method in trait Seq:

scala> a.sum
res: Int = 4296

Folding is a generalisation of reducing where we can specify the initial value from which the reducing starts:

scala> a.fold(0)(_ + _)
res: Int = 4296

scala> a.fold(100)(_ + _)
res: Int = 4396

Scanning. Scanning generalises folding by recording all the intermediate values during a fold when we traverse the sequence from left to right (or right to left):

scala> a
res: Array[Int] = Array(752, 884, 995, 462, 126, 632, 445)

scala> a.scanLeft(0)(_ + _) // running sum left-to-right
res: Array[Int] = Array(0, 752, 1636, 2631, 3093, 3219, 3851, 4296)

scala> a.scanRight(0)(_ + _) // running sum right-to-left
res: Array[Int] = Array(4296, 3544, 2660, 1665, 1203, 1077, 445, 0)

scala> a.scanLeft(100)(_ + _) // start sum from 100
res: Array[Int] = Array(100, 852, 1736, 2731, 3193, 3319, 3951, 4396)

And beyond. In the exercises we get yet further practice with sequence transformations and transformations on pairs of sequences such as zipping two sequences into a sequence of pairs:

scala> Array(1,2,3) zip Array(4,5,6)
res: Array[(Int, Int)] = Array((1,4), (2,5), (3,6))

The dual operation of unzipping breaks a sequence of pairs into two sequences:

scala> Array((10,1),(20,2),(30,3)).unzip
res: (Array[Int], Array[Int]) = (Array(10, 20, 30),Array(1, 2, 3))

For working with pairs, recall that you can index the components of a tuple object (such as a pair of integers) with the underscore notation. To illustrate this, let us define a pair of integers:

scala> val x = (123,456)
x: (Int, Int) = (123,456)

We can now index the pair as follows:

scala> x._1
res: Int = 123

scala> x._2
res: Int = 456