Struct im::conslist::ConsList
[−]
[src]
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 Arc
s, and insertion
operations accept any value for which there's a From
implementation into Arc<A>
. Iterators and lookup
operations, conversely, produce Arc<A>
.
Methods
impl<A> ConsList<A>
[src]
fn new() -> ConsList<A>
[src]
Construct an empty list.
fn singleton<R>(v: R) -> ConsList<A> where
R: Shared<A>,
[src]
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>,
[src]
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
[src]
Test whether a list is empty.
Time: O(1)
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)
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)
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)
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)
fn uncons2(&self) -> Option<(Arc<A>, Arc<A>, ConsList<A>)>
[src]
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());
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] );
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] );
fn iter(&self) -> Iter<A>
[src]
Get an iterator over a list.
fn sort_by<F>(&self, cmp: F) -> ConsList<A> where
F: Fn(Arc<A>, Arc<A>) -> Ordering,
[src]
F: Fn(Arc<A>, Arc<A>) -> Ordering,
Sort a list using a comparator function.
Time: O(n log n)
impl ConsList<i32>
[src]
fn range(from: i32, to: i32) -> ConsList<i32>
[src]
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,
[src]
A: Ord,
fn insert<T>(&self, item: T) -> ConsList<A> where
T: Shared<A>,
[src]
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>
[src]
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>
[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> 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.
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?
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>,