Crate slist 

s(tatic|tack)lists Experimental algebraic lists with with statically determined size that live on stack. They can be iterated over, mapped, folded, filtered and have continuous storage. #![no_std], no const generics, no macros, no unsafe, no heap allocation nor boxing, no dynamic dispatch, no dependencies, no unstable code used for the implementation. Just the Rust trait system.

Lists are constructed kind of like natural numbers in Peano arithmetic. For example, the type of a list with 8 elements is

let l: List<T, List<T, List<T, List<T, List<T, List<T, List<T, List<T, ()>>>>>>>>;

When the list is filtered, the result can be an arbitrary sublist, so the returned type is a disjuncion of all lists smaller than the original:

let s: Either<List<T, List<T, List<T, List<T, List<T, List<T, List<T, List<T, ()>>>>>>>>, Either<List<T, List<T, List<T, List<T, List<T, List<T, List<T, ()>>>>>>>, Either<List<T, List<T, List<T, List<T, List<T, List<T, ()>>>>>>, Either<List<T, List<T, List<T, List<T, List<T, ()>>>>>, Either<List<T, List<T, List<T, List<T, ()>>>>, Either<List<T, List<T, List<T, ()>>>, Either<List<T, List<T, ()>>, Either<List<T, ()>, Either<(), Void>>>>>>>>>;

Although very cumbersome to write, in the actual implementation, it has linear memory efficienncy and is only one tag longer than the original, which is as short as it can get, since the length is determined only on runtime. This way, computations can be performed on lists with variable but bounded length.

slist macro can be used for quick list creation (the actual implementation contains no macros):

use slist::prelude::*;

let list = slist![0_usize, 3, 10, 19, 12, 22, 28, 13, 6].map(|i| i + 1);
let filtered = list.filter(|u| (u % 2) == 0);
assert_eq!(filtered + slist![3, 4, 5], slist![4, 20, 14, 3, 4, 5]);
assert_eq!(slist![6, 7] * slist![false, true], slist![(6, false), (7, false), (6, true), (7, true)]);

let mut list = slist![4, 5, 6];
for i in list.as_mut() {
    *i += 2;
}
assert_eq!(list, slist![6, 7, 8]);

Note that when provided with an expression and size, the slist macro evaluates the expression for each element separately. This is different to the array constructor (or the vec macro) and can be used to iteratively build bounded lists, like of numbers from the standard input:

use slist::prelude::*;

let stdin = std::io::stdin();
let mut inputs = stdin.lock().lines().filter_map(Result::ok).map(|s| s.parse::<u16>().ok());

let list = slist![inputs.next().flatten(); 4];
let list = list.filter_map(|i| i);

The macros are only used for convenience and are not necessary for the library to function. For example, the preceding code gets expanded to:

let list = {
    use slist::List;
    let list: List<(), List<(), List<(), List<(), List<(), ()>>>>> = Default::default();
    list.map(|_| inputs.next().flatten())
};

If you prefer to write natural numbers in Peano form, there is no need for any macros at all.

Unfortunately, until generic associated types are stabilised, mapping of lists, resp. creating a list of references from a reference of a list need to be provided by separate traits, SlistMap<T, U>, resp. SlistAsRef<'a, T>. This crate provides a prelude module, from which every such trait can be conveniently imported.

This crate can take a heavy toll on the compiler and using in in production can be adventurous.

Modules

prelude

A helper module, exporting all traits for convenient working with lists.

Macros

slist

Creates a list containing the arguments.

slist_typegen

Generate a type of a list of units (()) of the given length. The only valid input is a non-negative integer literal. The type List of the slist crate needs to be imported in order for the resulting type to be parsed correctly.

Structs

List

A list type that contains an element of type T and another element, which is either another list type or unit (()). By convention, the given element is considered the last item on the list, although the compiler is free to rearrange the order as it feels.

Enums

Either

A disjuncion of two possible values. By nesting of Eithers, a disjuncion of lists of all lengths up to a certain bound is created.

Void

A type that cannot have an actual value, thus cannot ever be constructed.

Traits

Slist

A trait representing static stack lists.

SlistAsRef

A trait for creating a list of references from a reference of a list.

SlistFlatten

Flatten a list of lists of type U' into a list of U’

SlistMap

Map a list of type T into a list of type `U’ via a mapping closure.

SlistReverse

Reverse the direction of a list.

SlistSum

A disjunction of all the list types of type T, up to a certain length. Used for implementing filter for lists.