Homepage

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

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$$.

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