SeqGen: A Library for Sequence Generation

crazyrat13 — Tue, 12 Dec 2023 10:58:18 +0000

`0_` 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 sequence generation called SeqGen.

`1_` 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 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

`2_` Using The Library:

`2.0_` Dependencies:

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

`2.1_` 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 dependency to our project:

$ cargo add seqgen

Now we are ready to use the library.

`2.2_` Creating A Sequence:

In SeqGen, the sequence creation process maps directly to the two properties of the sequence that we concluded in What is A Sequence section, we have to define the initial elements and the function that produces the next element (called the transition function is 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 an new instance which 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 argument, and set it as the initial elements of the instance.

The second method is transition_function() which takes as argument a closure that represents the transition from the currently available elements to 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 illustration of the transition function.

Current Element in Generation	alive_elements	current_element_index
`1`	`[0]`	`1`
`2`	`[0, 1]`	`2`
`3`	`[0, 1, 2]`	`3`
`n`	`[0, 1, 2, 3, …, n]`	`n`

NOTE: alive_elements is of type SequencePart, we will take a look at the SequencePart type later in this article

Since the index of 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 alive 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 then 187 elements with this definition will cause u128 overflow. A better definition would use big int instead of u128.

`2.3_` 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 element with index of 0 to the element with 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 element 0 to 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
...

NOTE: The sequence we define are lazy, meaning the elements won’t be generated unless needed (in case of iteration), or explicitly requested (using the nth_element() method).

`2.4_` 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 alive 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 to 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, the Err variant is RangeError. The RangeError could be 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 DeadRangeerror 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 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.

`3_` 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.

DEV Community: crazyrat13

SeqGen: A Library for Sequence Generation

0_ Introduction:

1_ What is A Sequence:

2_ Using The Library:

2.0_ Dependencies:

2.1_ Creating A Project:

2.2_ Creating A Sequence:

2.3_ Using The Sequence:

2.4_ Working with Parts of The Sequence:

3_ Outroduction: