Static, cyclic, infinite lists with Seq


#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.


Ring reference structs