Struct im::list::List
[−]
[src]
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>
[src]
fn new() -> Self
Construct an empty list.
fn singleton<R>(a: R) -> Self where
Arc<A>: From<R>,
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>,
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>,
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>,
R: Borrow<Self>,
fn cons<R>(&self, a: R) -> Self where
Arc<A>: From<R>,
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>,
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>,
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>,
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,
F: Fn(Arc<A>, Arc<A>) -> Ordering,
Sort a list using a comparator function.
Time: O(n log n)
impl List<i32>
[src]
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>
[src]
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>,
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>
[src]
fn clone(&self) -> Self
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
Performs copy-assignment from source
. Read more
impl<A> Default for List<A>
[src]
impl<A> Add for List<A>
[src]
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>
[src]
fn eq(&self, other: &Self) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &Rhs) -> bool
1.0.0
This method tests for !=
.
impl<A: Eq> Eq for List<A>
[src]
impl<A: PartialOrd> PartialOrd for List<A>
[src]
fn partial_cmp(&self, other: &Self) -> Option<Ordering>
This method returns an ordering between self
and other
values if one exists. Read more
fn lt(&self, other: &Rhs) -> bool
1.0.0
This method tests less than (for self
and other
) and is used by the <
operator. Read more
fn le(&self, other: &Rhs) -> bool
1.0.0
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
fn gt(&self, other: &Rhs) -> bool
1.0.0
This method tests greater than (for self
and other
) and is used by the >
operator. Read more
fn ge(&self, other: &Rhs) -> bool
1.0.0
This method tests greater than or equal to (for self
and other
) and is used by the >=
operator. Read more
impl<A: Ord> Ord for List<A>
[src]
fn cmp(&self, other: &Self) -> Ordering
This method returns an Ordering
between self
and other
. Read more
impl<A: Hash> Hash for List<A>
[src]
fn hash<H: Hasher>(&self, state: &mut H)
Feeds this value into the given [Hasher
]. Read more
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0
H: Hasher,
Feeds a slice of this type into the given [Hasher
]. Read more
impl<A: Debug> Debug for List<A>
[src]
impl<A> IntoIterator for List<A>
[src]
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. Read more
impl<'a, A> IntoIterator for &'a List<A>
[src]
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. Read more
impl<A> Sum for List<A>
[src]
fn sum<I>(it: I) -> Self where
I: Iterator<Item = Self>,
I: Iterator<Item = Self>,
Method which takes an iterator and generates Self
from the elements by "summing up" the items. Read more
impl<A, T> FromIterator<T> for List<A> where
Arc<A>: From<T>,
[src]
Arc<A>: From<T>,
fn from_iter<I>(source: I) -> Self where
I: IntoIterator<Item = T>,
I: IntoIterator<Item = T>,
Creates a value from an iterator. Read more
impl<'a, A, T> From<&'a [T]> for List<A> where
Arc<A>: From<&'a T>,
[src]
Arc<A>: From<&'a T>,
impl<A, T> From<Vec<T>> for List<A> where
Arc<A>: From<T>,
[src]
Arc<A>: From<T>,
impl<'a, A, T> From<&'a Vec<T>> for List<A> where
Arc<A>: From<&'a T>,
[src]
Arc<A>: From<&'a T>,