Struct im::conslist::ConsList

pub struct ConsList<A>(_);

An implementation of immutable proper cons lists.

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

Items in the list are stored in Arcs, and insertion operations accept any value for which there's a Shared implementation into Arc<A>. Iterators and lookup operations, conversely, produce Arc<A>.

Methods

impl<A> ConsList<A>

fn new() -> ConsList<A>

Construct an empty list.

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

Construct a list with a single element.

fn from<R, I>(it: I) -> ConsList<A> where
    I: IntoIterator<Item = R>,
    R: Shared<A>, 

Construct a list by consuming an IntoIterator.

Allows you to construct a list out of anything that implements the IntoIterator trait.

Time: O(n)

Examples

assert_eq!(
  ConsList::from(vec![1, 2, 3, 4, 5]),
  conslist![1, 2, 3, 4, 5]
);

fn is_empty(&self) -> bool

Test whether a list is empty.

Time: O(1)

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)

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

Get the first element of a list.

If the list is empty, None is returned.

Time: O(1)

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)

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)

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

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());

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]
);

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]
);

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

Get an iterator over a list.

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)

impl ConsList<i32>

fn range(from: i32, to: i32) -> ConsList<i32>

Construct a list of numbers between from and to inclusive.

Examples

assert_eq!(
  ConsList::range(1, 5),
  conslist![1, 2, 3, 4, 5]
);

impl<A> ConsList<A> where
    A: Ord, 

fn insert<T>(&self, item: T) -> ConsList<A> where
    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]
);

fn sort(&self) -> ConsList<A>

Sort a list.

Time: O(n log n)

Examples

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

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?

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.