Struct im::conslist::ConsList
[−]
[src]
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>
[src]
pub fn new() -> ConsList<A>
[src]
Construct an empty list.
pub fn singleton<R>(v: R) -> ConsList<A> where
R: Shared<A>,
[src]
R: Shared<A>,
Construct a list with a single element.
pub fn is_empty(&self) -> bool
[src]
Test whether a list is empty.
Time: O(1)
pub fn cons<R>(&self, car: R) -> ConsList<A> where
R: Shared<A>,
[src]
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>>
[src]
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>>
[src]
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>)>
[src]
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>)>
[src]
pub fn len(&self) -> usize
[src]
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>,
[src]
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>
[src]
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>pub fn iter(&self) -> Iter<A>
[src]
Get an iterator over a list.
pub fn sort_by<F>(&self, cmp: F) -> ConsList<A> where
F: Fn(&A, &A) -> Ordering,
[src]
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
[src]
pub fn insert<T>(&self, item: T) -> ConsList<A> where
A: Ord,
T: Shared<A>,
[src]
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,
[src]
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>
[src]
fn clone(&self) -> Self
[src]
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)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl<A> Default for ConsList<A>
[src]
impl<A> PartialEq for ConsList<A> where
A: PartialEq,
[src]
A: PartialEq,
fn eq(&self, other: &ConsList<A>) -> bool
[src]
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
1.0.0[src]
This method tests for !=
.
impl<A> Eq for ConsList<A> where
A: Eq,
[src]
A: Eq,
impl<A> Hash for ConsList<A> where
A: Hash,
[src]
A: Hash,
fn hash<H>(&self, state: &mut H) where
H: Hasher,
[src]
H: Hasher,
Feeds this value into the given [Hasher
]. Read more
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
Feeds a slice of this type into the given [Hasher
]. Read more
impl<'a, A> Add for &'a ConsList<A>
[src]
type Output = ConsList<A>
The resulting type after applying the +
operator.
fn add(self, other: Self) -> Self::Output
[src]
Performs the +
operation.
impl<A> Add for ConsList<A>
[src]
type Output = Self
The resulting type after applying the +
operator.
fn add(self, other: Self) -> Self::Output
[src]
Performs the +
operation.
impl<A> Debug for ConsList<A> where
A: Debug,
[src]
A: Debug,
fn fmt(&self, f: &mut Formatter) -> Result<(), Error>
[src]
Formats the value using the given formatter. Read more
impl<A> IntoIterator for ConsList<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?
ⓘImportant traits for Iter<A>fn into_iter(self) -> Iter<A>
[src]
Creates an iterator from a value. Read more
impl<A> Sum for ConsList<A>
[src]
fn sum<I>(it: I) -> Self where
I: Iterator<Item = Self>,
[src]
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 ConsList<A> where
T: Shared<A>,
[src]
T: Shared<A>,
fn from_iter<I>(source: I) -> Self where
I: IntoIterator<Item = T>,
[src]
I: IntoIterator<Item = T>,
Creates a value from an iterator. Read more
impl<'a, A, R> From<&'a [R]> for ConsList<A> where
&'a R: Shared<A>,
[src]
&'a R: Shared<A>,
impl<A, R> From<Vec<R>> for ConsList<A> where
R: Shared<A>,
[src]
R: Shared<A>,
impl<'a, A, R> From<&'a Vec<R>> for ConsList<A> where
&'a R: Shared<A>,
[src]
&'a R: Shared<A>,