# Sequences

A sequence is a mathematical collection of objects in a particular order

For example: \(A = (1, 3, 2)\), in that order. A sequence \(( a, b, c )\) can be seen as the total bijective function \(\{ (1, a), (2, b), (3, c) \}\). Following this definition, we can access the \(n\) element of a sequence using function application notation. Given \(A = (a, c, b)\), \(A(2) = c\).

The empty sequence is defined as \(()\). Sequences are homogeneous. They must contain elements of the same type.

## Basic Operations

### Concatenation

Given sequences \(s\) and \(t\), their concatenation is denoted as \(s \frown t\). Notice that \(s \frown t \neq t \frown s\). Of course, \(s \frown () = s\), and concatenation is an associative operation.

### Filtering

Given a sequence \(s\), the sequence \(s \restriction x\) represents all the elements of \(s\) that are included in \(x\), preserving the ordering. For example, \(s = (a, b, b, a, c, b, a) \restriction (a, c) = (a, a, c, a)\).

Filtering the empty sequence always yields back the empty sequence.

### Head

The first element of a sequence is called its head. For example, \(head (a, b, c) = a\). The head of the empty sequence is the empty sequence.

### Tail

The tail of a sequence is a sequence containing all the original elements except for the first one. For example, \(tail (a, b, c) = (b, c)\). Notice that for any sequence \(s\), \(s = (head(s)) \frown tail(s)\).

### Cardinality

Since a sequence is a relation from natural numbers to the sequence elements, we can re-use the cardinality notation from sets. Thus, \(\vert (a, b, b, c) \vert = 4\), or \(\#(a, b, b, c) = 4\).

### Flattening

A sequence containing other sequences might be flattened to a single sequence by using a ditributed version of the concatenation operator. Given \(s = ((a, b, c), (d, e), (f, g))\), \(\frown/s = (a, b, c, d, e, f, g) \).

## Properties

### Injection

An injective sequence is one where its elements donâ€™t appear more than once. Remember that sequences are defined as functions whose range is the set of natural numbers, and therefore the functional definition of injection (one-to-one) holds: a sequence without duplicates is one where every natural number from the domain points to a different element.