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

Implementations

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

Get the two first elements and the tail of a list.

This function performs both the head function twice and the tail function in one go, returning a tuple of the double 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.uncons2() {
    None => (),
    Some((ref head, ref head2, ref tail)) => {
      print!("{:?} {:?}", head, head2);
      walk_through_list(tail)
    }
  }
}

Time: O(1)

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

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(&A, &A) -> Ordering, 

Sort a list using a comparator function.

Time: O(n log n)

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

Compare the Arc pointers of two ConsList

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, A> Add<&'a ConsList<A>> for &'a ConsList<A>

type Output = ConsList<A>

The resulting type after applying the + operator.

fn add(self, other: Self) -> Self::Output

Performs the + operation.

impl<A> Add<ConsList<A>> for ConsList<A>

type Output = Self

The resulting type after applying the + operator.

fn add(self, other: Self) -> Self::Output

Performs the + operation.

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> Debug for ConsList<A> where
    A: Debug, 

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

Formats the value using the given formatter.

impl<A> Default for ConsList<A>

fn default() -> Self

Default for lists is the empty list.

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, A, R> From<&'a Vec<R, Global>> for ConsList<A> where
    &'a R: Shared<A>, 

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

Performs the conversion.

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

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

Performs the conversion.

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> 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> IntoIterator for ConsList<A>

type IntoIter = Iter<A>

Which kind of iterator are we turning this into?

type Item = Arc<A>

The type of the elements being iterated over.

fn into_iter(self) -> Iter<A>

Creates an iterator from a value.

impl<A> PartialEq<ConsList<A>> 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> Sum<ConsList<A>> 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> Eq for ConsList<A> where
    A: Eq,