Struct im::list::List

pub struct List<A>(_);

A catenable list of values of type A.

A data structure like the simple ConsList but with efficient (generally O(1) in the worst case) add and remove operations on both ends.

If you need a list but haven't thought hard about your performance requirements, this is most likely the list you want. If you're mostly going to be consing and unconsing, and you have a lot of data, or a lot of lists, you might want the ConsList instead. When in doubt, choose the List.

Methods

impl<A> List<A>

fn new() -> Self

Construct an empty list.

fn singleton<R>(a: R) -> Self where
    Arc<A>: From<R>, 

Construct a list with a single value.

fn from<R, I>(it: I) -> List<A> where
    I: IntoIterator<Item = R>,
    Arc<A>: From<R>, 

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!(
  List::from(vec![1, 2, 3, 4, 5]),
  list![1, 2, 3, 4, 5]
);

fn is_empty(&self) -> bool

Test whether a list is empty.

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, list![1, 2, 3, 4, 5].len());

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

Get the first element of a list.

If the list is empty, None is returned.

fn tail(&self) -> Option<Self>

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.

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

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

Examples

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

fn link<R>(&self, other: R) -> Self where
    R: Borrow<Self>, 

fn cons<R>(&self, a: R) -> Self where
    Arc<A>: From<R>, 

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

fn push_front<R>(&self, a: R) -> Self where
    Arc<A>: From<R>, 

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

fn snoc<R>(&self, a: R) -> Self where
    Arc<A>: From<R>, 

Construct a list with a new value appended to the back of the current list.

snoc, for the curious, is cons spelled backwards, to denote that it works on the back of the list rather than the front. If you don't find that as clever as whoever coined the term no doubt did, this method is also available as List::push_back().

fn push_back<R>(&self, a: R) -> Self where
    Arc<A>: From<R>, 

Construct a list with a new value appended to the back of the current list.

fn uncons(&self) -> Option<(Arc<A>, List<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: &List<A>) where A: Debug {
    match list.uncons() {
        None => (),
        Some((ref head, ref tail)) => {
            print!("{:?}", head);
            walk_through_list(tail)
        }
    }
}

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

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

Get an iterator over a list.

fn reverse(&self) -> Self

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

Time: O(n)

Examples

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

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

Sort a list using a comparator function.

Time: O(n log n)

impl List<i32>

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

Construct a list of numbers between from and to inclusive.

Examples

assert_eq!(
  List::range(1, 5),
  list![1, 2, 3, 4, 5]
);

impl<A: Ord> List<A>

fn sort(&self) -> Self

Sort a list of ordered elements.

Time: O(n log n)

Examples

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

fn insert<T>(&self, item: T) -> Self where
    Arc<A>: From<T>, 

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!(
  list![2, 4, 6].insert(5).insert(1).insert(3),
  list![1, 2, 3, 4, 5, 6]
);

Trait Implementations

impl<A> Clone for List<A>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<A> Default for List<A>

fn default() -> Self

Returns the "default value" for a type.

impl<A> Add for List<A>

type Output = List<A>

The resulting type after applying the + operator

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

The method for the + operator

impl<A: PartialEq> PartialEq for List<A>

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

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=.

impl<A: Eq> Eq for List<A>

impl<A: PartialOrd> PartialOrd for List<A>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

This method tests less than (for self and other) and is used by the < operator.

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

This method tests less than or equal to (for self and other) and is used by the <= operator.

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

This method tests greater than (for self and other) and is used by the > operator.

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

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<A: Ord> Ord for List<A>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

impl<A: Hash> Hash for List<A>

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

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> Debug for List<A>

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

Formats the value using the given formatter.

impl<A> IntoIterator for List<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) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, A> IntoIterator for &'a List<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) -> Self::IntoIter

Creates an iterator from a value.

impl<A> Sum for List<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 List<A> where
    Arc<A>: From<T>, 

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

Creates a value from an iterator.

impl<'a, A, T> From<&'a [T]> for List<A> where
    Arc<A>: From<&'a T>, 

fn from(slice: &'a [T]) -> List<A>

Performs the conversion.

impl<A, T> From<Vec<T>> for List<A> where
    Arc<A>: From<T>, 

fn from(vec: Vec<T>) -> List<A>

Performs the conversion.

impl<'a, A, T> From<&'a Vec<T>> for List<A> where
    Arc<A>: From<&'a T>, 

fn from(vec: &'a Vec<T>) -> List<A>

Performs the conversion.