# 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
```