Request for comments: module seq implementing sequence container


#1

Hello all,

In the past I missed an implementation of a generic, lightweight, stack-oriented linked lists in Rust std-library.

To close the gap, I implemented the small module seq providing the generic sequence container Seq (v 0.1.0)
https://crates.io/crates/seq

I would like to improve the implementation, please feel free to comment.

As short description:

Seq is a lightweight container of data sequences, data being stacked on top of each other.

A sequence can be Empty or a construction Cons* of a value (called head aka first ft) on top of another
sequence (called tail aka rest rt). Sequences are formed of immutable data elements; multiple sequences may share
the same tail, permitting compact representation of hierarchical data.

The sequence container Seq allows to construct dynamic, linked lists; each element of the sequence is one of the
following variants:

  • Empty: The empty sequence <>
  • ConsRef(head, tail): Constructs a new sequence with head being the first element and tail referencing another, borrowed sequence: head|tail. This variant permits construction of sequences using stack-allocated data solely".
  • ConsOwn(head, boxedtail): Constructs a new sequence with head being the first element and tail referencing another, owned, boxed sequence: head|boxedtail. Here the tail is residing in heap allocated memory. This variant permits construction of sequences using heap-allocated dynamic data.

These variants may be combined with each other, representing a mixture of borrowed and owned elements. The memory safety feature of Rust
allows automated and correct management of lifetime of each element of the sequence.

The lifetime of each element of the sequence depends on the function context
it has been added to the top of the sequence; ‘Empty’ is the element with longest lifetime.

In first place Seq is intended as lightweight, dynamic, stack-allocated, linked list for use cases such as traversing tree-structures.
Traversal may be done using visitor pattern or nested functions calls; the top-most element of the sequence representing the current traversal context.
In the ideal scenarios no dynamic memory allocation shall be involved.

The sequence type Seq implements the trait IntoIterator, enabling the usage of Rust’s iterator framework.