# Sequences

Sequences provides most of the operations from real and complex vectors, but avoiding the storage. Sequences are similar to enumerable types in C# with LINQ, and are a requisite for any functional language.

AUSTRA supports three kinds of sequences: seq, for real valued sequences, cseq for complex ones, and iseq, for integer sequences.

Let's say we want to calculate factorials. AUSTRA is a functional language, so we don't have explicit loops. We could, however, do this with a vector:

The above code works fine, but it forces the library to allocate one array of ten items. This is the alternative, using a sequence:

Since the sequence's values are generated only by demand, there's no need for the internal storage.

These are the class methods for seq:

seq::new | Creates a sequence, either from a range, a range and a step, or from a vector or matrix. See examples below. |

seq::random | Creates a sequence of random values. |

seq::nrandom | Creates a sequence of random values, using a normal distribution. |

seq::ar | Creates a sequence using an AutoRegressive process. |

seq::ma | Creates a sequence using a Moving Average process. |

seq::unfold | Generate values from a seed and a generating function. |

This code fragment shows some of the available constructors for sequences:

```
seq(1, 10); -- Numbers from 1 to 10.
seq(10, 1); -- The inverted sequence.
```

**seq::**new(1, 10); -- ::new was omitted before.
seq(0, 128, τ); -- A uniform grid with 128 intervals.
seq(v); -- A sequence from a vector.
seq([sqrt(2), e, π, τ]);
seq(v1^v2); -- A sequence from a matrix.**seq::**random(10); -- A sequence with 10 random values.

**seq::**nrandom(10), -- A sequence with 10 Gaussian random values.

**seq::**nrandom(10, 2) -- Ten normal samples with variance = 2.

Real sequences created with just a lower and an upper bound are always based on integer bounds. For instance, these two expressions represent the same real sequence:

```
seq(1, 10); -- Numbers from 1 to 10.
seq(1.5, 10.6); -- Numbers from 1 to 10, too.
```

The reason for this rule is that these sequences have always one unit as their step. It is easier to reason about their behaviour knowing that their boundaries always are integer values.

There are two additional class methods for generating autoregressive, AR(p), and moving average, MA(q), sequences:

`-- An autoregressive (AR) process of order three.`

**seq::**ar(1000, 1, [0.1, 0.05, 0.01]);
-- A moving average (MA) process of order three.
-- The first term in the vector is the model's mean.

**seq::**ma(1000, 1, [0, 0.1, 0.05, 0.01])

You can materialize the content of a sequence as a vector using the toVector property:

Another class method for creating sequences is seq::unfold (see Unfold), which has three variants:

`-- Powers of 2, from 2 to 1024.`

**seq::**unfold(10, 2, x => 2x);
-- Maclaurin series for exp(1).

**seq::**unfold(100000, 1, (n, x) => x / (n + 1)).sum + 1;
-- Real-valued Fibonacci sequence.

**seq::**unfold(50, 1, 1, (x, y) => x + y);

The unfold sequence generator is important for the language since it can express iterative behaviour in a language with no explicit loops and conditionals. The alternative to iteration is recursion, which is also provided by AUSTRA, but a recursive function is almost always more expensive, even in the presence of tail optimizations.

Let us consider, for instance, how we would write a function for the greatest common divisor. When learning about function definitions, we saw that we could define a recursive function for this task:

`-- The recursive version`

**def** gcd1:"Recursive GCD"(a, b: **int**): **int** =
**let** rm = a % b **in**
iff(rm = 0, b, mcd(b, rm))

This is a fine recursive definition that even is amenable to tail recursion optimization. Now compare with the iterative alternative:

`-- -- The iterative version`

**def** gcd2:"Iterative GCD"(a, b: **int**): **int** =
iseq::unfold(10000, a, b, (x, y) => x%y).while(x => x > 0).last

Even though it looks more verbose, the second definition is almost twice faster than the recursive definition. Note, however, that we have used the class iseq instead of seq, so the property last directly returned an integer value. We could have kept seq by simply adding toInt after calling last:

**def** gcd3:"Iterative GCD"(a, b: **int**): **int** =
seq::unfold(10000, a, b, (x, y) => x%y).while(x => x > 0).last.toInt

Still, the advantage of the iterative definition will be huge compared to the recursive definition.

Two things to have into account:

- Have we not included the while method, every call to that unfold sequence would end with failure as soon as the algorithm would have tried to divide by zero. The while method avoids that problem and gives as the value we need.
- The unfold generator requires a first parameter stating how many values to create. We could have devised a variant of unfold for creating infinite length sequence. I have preferred, however, to put the burden of picking a high enough value on your shoulders. It is security against convenience.

These are the properties supported by sequences of real values:

acf | The Autocorrelation function. See ACF. |

distinct | Select unique values in the sequence, with no predefined order. See Distinct. |

fft | Calculates a Fast Fourier Transform. See Fft. |

first | Gets the first term of the sequence. See First. |

last | Gets the last term of the sequence. See Last. |

length | Gets the number of elements in the sequence. See Length. |

max | Get the maximum value in the sequence. See Max. |

min | Get the minimum value in the sequence. See Min. |

pacf | The Partial Autocorrelation function. See PACF. |

plot | Plots the sequence. See Plot. |

prod | Multiplies all values in the sequence. See Product. |

sort | Sorts values in ascending order. See Sort. |

sortDesc | Sorts values in descending order. See SortDescending. |

stats | Gets all statistic moments of the sequence. See Stats. |

sum | Sums all values in the sequence. See Sum. |

toVector | Materializes the sequence into a vector. See ToVector. |

These are the methods that can be used with a sequence of real values:

all | Checks if all items in the sequence satisfy a predicate. See All. |

any | Checks if there is an item in the sequence satisfying a predicate. See Any. |

ar | Estimates coefficients for an AR(p) model. See AutoRegression. |

arModel | Creates a full AR(p) model. See ARModel. |

filter | Returns items of the original sequence satisfying a predicate. See Filter. |

ma | Estimates coefficients for an MA(q) model. See MovingAverage. |

maModel | Creates a full MA(q) model. See MAModel. |

map | Transforms items with the help of a lambda function. See Map. |

reduce | Conflates all values in a sequence using a lambda. See Reduce. |

until | Returns a prefix of a sequence until a values satisfying a predicate is found. See Until. |

while | Returns a prefix of a sequence while values satisfy a predicate. See While. |

zip | Combines two sequences using a lambda function. See Zip. |

As seen before, the while method excludes from its returning sequence the first value satisfying its predicate. On the contrary, until includes that very value in the returning sequence.

Sequence operators mimics most of vector's operators.

`seq(1, 10) * seq(10, 1) -- The dot product.`

For instance, simple operators can be used to change the underlying distribution of a random sequence.

**seq::**random(100) * 2 - 1;
-- Check the moments of the above distribution.
(**seq::**random(100) * 2 - 1).stats

Unary operators for sequences could, in theory, be implemented using map, and binary operators can also be written using zip.

However, in most cases, having an explicit operator results in a faster implementation. It is most evident for sequences backed by a vector, but it also happens for other kinds of sequences. For instance, when a range or grid sequence is negated, you can implement the result using another range or grid sequence.

Integer sequences are represented by the iseq class.

These are the class methods supported by iseq:

iseq::new | Creates a sequence, either from a range, a range and a step, or from an integer vector. |

iseq::random | Creates a sequence of random integers. You can pass an upper bound, or an interval for values. |

iseq::unfold | Similar to seq::unfold, but with integer arguments. |

These properties can be used with integer sequences:

distinct | Select unique values in the sequence, with no predefined order. See Distinct. |

first | Gets the first term of the sequence. See First. |

last | Gets the last term of the sequence. See Last. |

length | Gets the number of elements in the sequence. See Length. |

max | Get the maximum value in the sequence. See Max. |

min | Get the minimum value in the sequence. See Min. |

plot | Plots the sequence. See Plot. |

prod | Multiplies all values in the sequence. See Product. |

sort | Sorts values in ascending order. See Sort. |

sortDesc | Sorts values in descending order. See SortDescending. |

stats | Gets all statistic moments of the sequence. See Stats. |

sum | Sums all values in the sequence. See Sum. |

toVector | Materializes the sequence into a vector. See ToVector. |

These are the available methods:

all | Checks if all items in the sequence satisfy a predicate. See All. |

any | Checks if there is an item in the sequence satisfying a predicate. See Any. |

filter | Returns items of the original sequence satisfying a predicate. See Filter. |

map | Transforms items with the help of a lambda function. See Map. |

mapReal | Transforms items with the help of a lambda function. See MapReal. |

reduce | Conflates all values in a sequence using a lambda. See Reduce. |

until | Returns a prefix of a sequence until a values satisfying a predicate is found. See Until. |

while | Returns a prefix of a sequence while values satisfy a predicate. See While. |

zip | Combines two sequences using a lambda function. See Zip. |

This example shows how to calculate the Collatz sequence using integer sequences:

**let** collatz(n: **int**) =
**iseq::**unfold(1000000, n, x => iff(x % 2 = 0, x / 2, 3x + 1))
.until(x => x = 1);
collatz(137)

Though the generator is created with a big enough upper limit, the sequence stops when a 1 is generated. The until method can also be written this way:

**let** collatz(n: **int**) =
**iseq::**unfold(1000000, n, x => iff(x % 2 = 0, x / 2, 3x + 1))
.until(1)

Complex sequences can also be used, with the cseq class.

These are the class methods supported by cseq:

cseq::new | Creates a sequence, either from a complex interval, or from a complex vector. |

cseq::random | Creates a sequence of random values from a uniform distribution. |

cseq::nrandom | Creates a sequence of random values with a standard normal distribution. |

cseq::unfold | Similar to seq::unfold, but with complex arguments. |

These properties can be used with complex sequences:

distinct | Select unique values in the sequence, with no predefined order. See Distinct. |

first | Gets the first term of the sequence. See First. |

last | Gets the last term of the sequence. See Last. |

length | Gets the number of elements in the sequence. See Length. |

plot | Plots the sequence. See Plot. |

prod | Multiplies all values in the sequence. See Product. |

sum | Sums all values in the sequence. See Sum. |

toVector | Materializes the sequence into a complex vector. See ToVector. |

And these are the available methods:

all | Checks if all items in the sequence satisfy a predicate. See All. |

any | Checks if there is an item in the sequence satisfying a predicate. See Any. |

filter | Returns items of the original sequence satisfying a predicate. See Filter. |

map | Transforms items with the help of a lambda function. See Map. |

mapReal | Transforms items with the help of a lambda function. See MapReal. |

reduce | Conflates all values in a sequence using a lambda. See Reduce. |

until | Returns a prefix of a sequence until a values satisfying a predicate is found. See Until. |

while | Returns a prefix of a sequence while values satisfy a predicate. See While. |

zip | Combines two sequences using a lambda function. See Zip. |

Sequence are modeled after .NET LINQ enumerables, and so many other functional libraries. One of the most interesting features of these libraries is *delayed execution*.

Applying a method or an operator on a sequence does not means that it will automatically scan the sequence values. Let's start with a simple example:

The above code first creates a sequence that will enumerate numbers from 1 to 1000. Creating the sequence means creating a small instance of an internal class that can be called later to yield the values in the sequence. The unary minus, however, take that sequence generator and returns another generator that yields values in descending order, from the interval *[-10, -1]*. It does not forces yet the sequence enumeration. Actually, enumeration takes place as the last operation, as you hit F5 in the AUSTRA desktop, as the application needs to print the values created by the expression. The same would happen with this expression, that plots the sequence as a series:

It is the plot method the trigger which starts the internal loop for generating all the values. You could even intercalate another method call before the plot, without triggering enumeration:

```
-- Sort the negated values in ascending order.
(-seq(1, 1000)).sort.plot;
-- Square values, select multiples of three and sort descending.
seq(1, 1000).map(x => x^2).filter(x => x % 3 = 0).sortDesc.plot;
-- Methods like sum, prod, any, all or first can also trigger evaluation.
seq(1, 100).filter(x => x % 2 = 0).map(x => x^2).sum
```