Struct im::conslist::ConsList

pub struct ConsList<A>(_);

An immutable proper cons lists.

The cons list is perhaps the most basic immutable data structure: a singly linked list built out of 'cons cells,' which are cells containing two values, the left hand value being the head of the list and the right hand value being a reference to the rest of the list, or a Nil value denoting the end of the list.

Structure can be shared between lists (and is reference counted), and append to the front of a list is O(1). Cons cells keep track of the length of the list at the current position, as an extra optimisation, so getting the length of a list is also O(1). Otherwise, operations are generally O(n).

Unless you know you want a ConsList, you're probably better off using a Vector, which has more efficient performance characteristics in almost all cases. The ConsList is particularly useful as an immutable stack where you only push and pop items from the front of the list. Beware that it has no mutable operations.

Methods

impl<A> ConsList<A>

pub fn new() -> ConsList<A>

Construct an empty list.

pub fn singleton<R>(v: R) -> ConsList<A> where
    R: Shared<A>, 

Construct a list with a single element.

pub fn is_empty(&self) -> bool

Test whether a list is empty.

Time: O(1)

pub fn cons<R>(&self, car: R) -> ConsList<A> where
    R: Shared<A>, 

Construct a list with a new value prepended to the front of the current list.

Time: O(1)

pub fn head(&self) -> Option<Arc<A>>

Get the first element of a list.

If the list is empty, None is returned.

Time: O(1)

pub fn tail(&self) -> Option<ConsList<A>>

Get the tail of a list.

The tail means all elements in the list after the first item (the head). If the list only has one element, the result is an empty list. If the list is empty, the result is None.

Time: O(1)

pub fn uncons(&self) -> Option<(Arc<A>, ConsList<A>)>

Get the head and the tail of a list.

This function performs both the head function and the tail function in one go, returning a tuple of the head and the tail, or None if the list is empty.

Examples

This can be useful when pattern matching your way through a list:

fn walk_through_list<A>(list: &ConsList<A>) where A: Debug {
    match list.uncons() {
        None => (),
        Some((ref head, ref tail)) => {
            print!("{:?}", head);
            walk_through_list(tail)
        }
    }
}

Time: O(1)

pub fn uncons2(&self) -> Option<(Arc<A>, Arc<A>, ConsList<A>)>

pub fn len(&self) -> usize

Get the length of a list.

This operation is instant, because cons cells store the length of the list they're the head of.

Time: O(1)

Examples

assert_eq!(5, conslist![1, 2, 3, 4, 5].len());

pub fn append<R>(&self, right: R) -> Self where
    R: Borrow<Self>, 

Append the list right to the end of the current list.

Time: O(n)

Examples

assert_eq!(
  conslist![1, 2, 3].append(conslist![7, 8, 9]),
  conslist![1, 2, 3, 7, 8, 9]
);

pub fn reverse(&self) -> ConsList<A>

Construct a list which is the reverse of the current list.

Time: O(n)

Examples

assert_eq!(
  conslist![1, 2, 3, 4, 5].reverse(),
  conslist![5, 4, 3, 2, 1]
);

Important traits for Iter<A>

impl<A> Iterator for Iter<A> type Item = Arc<A>;

pub fn iter(&self) -> Iter<A>

Get an iterator over a list.

pub fn sort_by<F>(&self, cmp: F) -> ConsList<A> where
    F: Fn(Arc<A>, Arc<A>) -> Ordering, 

Sort a list using a comparator function.

Time: O(n log n)

pub fn ptr_eq(&self, other: &Self) -> bool

pub fn insert<T>(&self, item: T) -> ConsList<A> where
    A: Ord,
    T: Shared<A>, 

Insert an item into a sorted list.

Constructs a new list with the new item inserted before the first item in the list which is larger than the new item, as determined by the Ord trait.

Time: O(n)

Examples

assert_eq!(
  conslist![2, 4, 6].insert(5).insert(1).insert(3),
  conslist![1, 2, 3, 4, 5, 6]
);

pub fn sort(&self) -> ConsList<A> where
    A: Ord, 

Sort a list.

Time: O(n log n)

Examples

assert_eq!(
  conslist![2, 8, 1, 6, 3, 7, 5, 4].sort(),
  ConsList::from_iter(1..9)
);

Trait Implementations

impl<A> Clone for ConsList<A>

fn clone(&self) -> Self

Clone a list.

Cons cells use Arc behind the scenes, so this is no more expensive than cloning an Arc reference.

Time: O(1)

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<A> Default for ConsList<A>

fn default() -> Self

Default for lists is the empty list.

impl<A> PartialEq for ConsList<A> where
    A: PartialEq, 

fn eq(&self, other: &ConsList<A>) -> bool

Test if two lists are equal.

This could potentially be an expensive operation, as we need to walk both lists to test for equality. We can very quickly determine equality if the lists have different lengths (can't be equal). Otherwise, we walk the lists to compare values.

Time: O(n)

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<A> Eq for ConsList<A> where
    A: Eq, 

impl<A> Hash for ConsList<A> where
    A: Hash, 

fn hash<H>(&self, state: &mut H) where
    H: Hasher, 

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

impl<A> Debug for ConsList<A> where
    A: Debug, 

fn fmt(&self, f: &mut Formatter) -> Result<(), Error>

Formats the value using the given formatter.

impl<A> IntoIterator for ConsList<A>

type Item = Arc<A>

The type of the elements being iterated over.

type IntoIter = Iter<A>

Which kind of iterator are we turning this into?

Important traits for Iter<A>

impl<A> Iterator for Iter<A> type Item = Arc<A>;

fn into_iter(self) -> Iter<A>

Creates an iterator from a value.

impl<A> Sum for ConsList<A>

fn sum<I>(it: I) -> Self where
    I: Iterator<Item = Self>, 

Method which takes an iterator and generates Self from the elements by "summing up" the items.

impl<A, T> FromIterator<T> for ConsList<A> where
    T: Shared<A>, 

fn from_iter<I>(source: I) -> Self where
    I: IntoIterator<Item = T>, 

Creates a value from an iterator.

impl<'a, A, R> From<&'a [R]> for ConsList<A> where
    &'a R: Shared<A>, 

fn from(slice: &'a [R]) -> Self

Performs the conversion.

impl<A, R> From<Vec<R>> for ConsList<A> where
    R: Shared<A>, 

fn from(vec: Vec<R>) -> Self

Performs the conversion.

impl<'a, A, R> From<&'a Vec<R>> for ConsList<A> where
    &'a R: Shared<A>, 

fn from(vec: &'a Vec<R>) -> Self

Performs the conversion.