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:

vec(10, i => i + 1).prod

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

seq(1, 10).prod

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

Sequence constructors

These are the class methods for seq:

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:

seq::random(10).toVector

The unfold sequence generator

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.

Methods and properties

These are the properties supported by sequences of real values:

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

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

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

Integer sequences are represented by the iseq class.

Class methods

These are the class methods supported by iseq:

Methods and properties

These properties can be used with integer sequences:

These are the available methods:

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.

Class methods

These are the class methods supported by cseq:

Methods and properties

These properties can be used with complex sequences:

And these are the available methods:

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:

-seq(1, 1000)

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:

(-seq(1, 1000)).plot

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

Reference

Other Resources