Crate persistent_list

A singly-linked persistent thread safe list

List is a basic singly-linked list which uses structural sharing and Arc + clone-on-write mechanics to provide a persistent thread safe list.

Because of the the structure is only cloned when it needs too it has relatively little overhead when no structural sharing occurs.

Immutability

Purist would probably never call this structure immutable as there many provided ways to modify the underlying data. However with respect to rusts strict mutability and borrowing mechanics this crate provides a way to have a persistent data structure which can share underlying memory / state, while still appearing immutable to everyone sharing. Even if somewhere some instance is declared as mutable and starts modifying their view.

Much inspiration was taken from the im crate. It is worth looking at as it gives both some great motivations for when and why to use these types of structures as well as providing some excellent implementations of the most important structural sharing persistent data structures Maps, Sets and Vectors (using HAMT, RRB trees and B-trees)

Examples

// list1 and list2 structurally share the data
let list1 = list![1,2,3,4];
let mut list2 = list1.clone();

// they still share a tail even if one starts
// to be modified.
assert_eq!(list2.pop_front(), Some(1));

// Every time around the loop they share less and
// less data
for i in &mut list2 {
    *i *= 2;
}

// Until finally no structural sharing is possible
assert_eq!(list1, list![1,2,3,4]); // unchanged
assert_eq!(list2, list![4,6,8]);   // modified

Macros

list	Construct a list from a sequence of elements.

Structs

IntoIter	An owning iterator over the elements of a List.
Iter	An iterator over the elements of a List.
IterMut	A mutable iterator over the elements of a List.
List	A singly-linked persistent thread safe list.

Functions

cons	Construct a List with a new element at the front of the current List.