SeqGen: The Library I Created for Sequence Generation

Introduction:

If you search the internet for a library that can generate sequences, you can hardly find one, although sequences are a core concept of discrete mathematics and computer science.

In this short article, we will take a look at a library I wrote for the sequence generation called SeqGen.

What Is A Sequence?

A sequence (informally speaking ) is a set of elements (mostly numbers) where the production of each element is based on the preceding element(s).

The most basic example is a simple linear sequence of positive integers where the first element is 0 and the next element is the preceding element plus one, so we can get the second element by adding one to the first one, and we can get the third element by adding one to second one, and so on. The linear sequence would look like this: {0, 1, 2, 3, …, n}.

A more complex example could be the Fibonacci sequence where the first two elements are 0 and 1, and the next element is the sum of the two preceding elements. The Fibonacci sequence would look like this: {0, 1, 1, 2, 3, 5, 8, 13, 21, …, n}

We can notice from above that a sequence is defined with two properties:

• The initial elements
• A function that produces the next element

Using the Library:

Dependencies:

The SeqGen library is written in the Rust programming language; to follow up, you need to have Rust installed.

Creating A Project:

Let’s create a new project to use the SeqGen library; we can do so with cargo:

$ cargo new --bin sequence && cd sequence

Now, let’s add the library as a dependency to our project:

$ cargo add seqgen

Now, we are ready to use the library.

Creating A Sequence:

In SeqGen, the sequence creation process maps directly to the two properties of the sequence that we concluded in the What is A Sequence section; we have to define the initial elements and the function that produces the next element (called the transition function in SeqGen).

Let’s create the linear sequence:

use seqgen::prelude::*;

fn main() {
    let linear_seq = Sequence::new()
        .initial_elements(vec![0])
        .transition_function(|alive_elements, current_element_index| {
            alive_elements.last_element().unwrap() + 1
        });
}

The Sequence type is a struct that represents a sequence; by calling the associated function new() on this type, we get a new instance that is undefined. On this undefined instance, we can call methods to define it.

The first method is initial_elements() which accepts a vector of elements as an argument, and sets it as the initial elements of the instance.

The second method is transition_function() which takes as an argument a closure that represents the transition from the currently available elements to the next element.

This closure has access to two arguments: the first is alive_elements which represents the currently available elements, and the second is current_element_index (of type usize) which is the index of the current element in generation. See the table below for an illustration of the transition function.

Since the index of the element is also its value in the linear sequence, we can simplify the example above to:

use seqgen::prelude::*;

fn main() {
    let linear_seq = Sequence::new().transition_function(|_, i| i);
}

Here, we do not need to define the initial elements, and we do not need access to the live elements; we just need the index (which is named i in this case), and we simply return it.

In the same manner, we can define the Fibonacci sequence:

use seqgen::prelude::*;

fn main() {
    let fib_seq = Sequence::new()
        .initial_elements(vec![0, 1_u128])
        .transition_function(|alive_elements, i| {
            let x = alive_elements.nth_element(i - 1).unwrap();
            let y = alive_elements.nth_element(i - 2).unwrap();

            x + y
        });
}

Since the Fibonacci sequence grows exponentially, generating more than 187 elements with this definition will cause u128 to overflow. A better definition would use big int instead of u128.

Using the Sequence:

After we defined our sequence, we can access its elements:

use seqgen::prelude::*;

fn main() {
    let mut linear_seq = Sequence::new().transition_function(|_, i| i);
    let some_element = linear_seq.nth_element(111);
    println!("{some_element}");
}

Here, we are accessing the 111th element using nth_element() method which returns an immutable reference to the element (&usize in this case).

Notice that we made linear_seq mutable. That’s because the nth_element() method will mutate the alive elements of the sequence.

In this way, we can access any element of the sequence (from the element with an index of 0 to the element with an index of usize::MAX .)

We can also iterate over the sequence like any Rust iterator:

use seqgen::prelude::*;

fn main() {
    let linear_seq = Sequence::new().transition_function(|_, i| i);
    linear_seq.for_each(|e| println!("{e}"));
}

This code will print all the elements of the sequence (from the element 0 to the element usize::MAX):

$ cargo run -q
0
1
2
3
4
5
6
7
8
9
10
11
12
13
...

We can get the odd elements from the sequence using the following code:

use seqgen::prelude::*;

fn main() {
    let linear_seq = Sequence::new().transition_function(|_, i| i);
    let odd_elements = linear_seq.filter(|e| e % 2 != 0);

    odd_elements.for_each(|e| println!("{e}"));
}

Output:

$ cargo run -q                                                            
1
3
5
7
9
11
13
...

Working With Parts of the Sequence:

Sometimes, we need to only work with parts of a sequence, in this case, we have sequence parts.

There are three types of the sequence part:

• AliveElementsPart
• ImmutableRangePart
• MutableRangePart

AliveElementsPart:

We can get the live elements using the alive_elements() method on the sequence:

use seqgen::prelude::*;

fn main() {
    let linear_seq = Sequence::new()
        .transition_function(|_, i| i)
        .pre_generate(111);

    let alive_elements = linear_seq.alive_elements();

    for alive_element in alive_elements {
        print!("{alive_element} ");
    }
}

This code will print all the alive elements (0 to 110 in this case because we pre-generated 111 elements).

ImmutableRangePart:

Immutable ranges are ranges of the alive elements; they cannot mutate the sequence. If you will create an immutable range and not all its elements are alive, you will get an error (DeadRange error).

We can create an immutable range using the range() method which returns a Result. The Ok variant is ImmutableRangePart, and the Err variant is RangeError . The RangeError could be the InvalidRange variant (in case the start of the range is greater than its end), or it could be DeadRange variant (in case not all elements of the range are alive):

use seqgen::prelude::*;

fn main() {
    let linear_seq = Sequence::new().transition_function(|_, i| i);
    let range = linear_seq.range(0, 3).unwrap();

    for e in range {
        println!("{e}")
    }
}

This code will panic with DeadRange error because there is no alive element. We can correct this with the following:

use seqgen::prelude::*;

fn main() {
    let mut linear_seq = Sequence::new().transition_function(|_, i| i);

    linear_seq.generate(3);

    let range = linear_seq.range(0, 3).unwrap();

    for e in range {
        println!("{e}")
    }
}

Here, we generated 3 elements to make the range valid.

MutableRangePart:

A mutable range can mutate the sequence (generate elements).

We can use a mutable range like so:

use seqgen::prelude::*;

fn main() {
    let mut linear_seq = Sequence::new().transition_function(|_, i| i);
    let mut_range = linear_seq.range_mut(0, 111).unwrap();

    for e in mut_range {
        println!("{e}");
    }
}

This code will print the elements from 0 to 110.

Outroduction:

Thank you for reading this article to the end, and I hope you found something useful in it. If you have any suggestions that can improve this library, please open an issue on GitHub, and if you want to contribute to the library, that would be wonderful.

Also published here