Static, cyclic, infinite lists with Seq

tutorials
1

The sequence container Seq defines a generic queue; each element within this queue has its individual lifetime; for example depending on the lexical scope the head-element has been attached to the queue.

The data type Seq is as simple as possible, it is just playing with lifetime declarations.

pub enum Seq<'a, T: 'a> {
    /// The empty sequence
    Empty,
    /// Constructing a sequence with head data and reference to a tail
    ConsRef(T, &'a Seq<'a, T>),
    /// Constructing a sequence with head data and reference to boxed tail
    ConsOwn(T, Box<Seq<'a, T>>),
}

If the elements in question are static, it turns out that the sequence container Seq can be used to form a cyclic, infinite data structure; without the use of any Box-type.

The following test-code from seq-repository demonstrates the definition of a cyclic, infinite data structure without any boxing. The infinite, cyclic data structure is formed by 4 elements/words. The iterator is taking 12 elements from infinite list and is counting the characters.

#[cfg(test)]
mod tests {
    use seq::Seq;

    struct MyData(&'static str);

    // this static ring has 4 elements, arranged to infinite, cyclic loop
    static CYC_A: Seq<MyData> = Seq::ConsRef(MyData("Forever"), &CYC_D); // len()==7
    static CYC_B: Seq<MyData> = Seq::ConsRef(MyData("Round"), &CYC_A); // len()==5
    static CYC_C: Seq<MyData> = Seq::ConsRef(MyData("And"), &CYC_B); // len()==3
    static CYC_D: Seq<MyData> = Seq::ConsRef(MyData("Round"), &CYC_C); // len()==5

    #[test]
    fn test_cyclic() {
        // take first 12 elements from cyclic ring and count the characters
        let sum = CYC_A.into_iter().take(3*4).fold(0, | x, y| x + y.0.len());
        assert_eq!(3*20, sum);
    }
}

This is possible, as each element in the sequence Seq possesses its individual lifetime, the data is unmovable once it is referenced as an element of a sequence Seq. These constraints are managed by Rust during compile time. Dealing with static lifetime now is a corner-case, permitting cyclic lists.
In contrast the containers such as LinkedList or Vector are managing elements of identical lifetime (AFAICS)

Hopefully this sandtable exercise is helpful for other developers.

3 Likes
2