Module im::conslist
[−]
[src]
A cons list.
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.
Structs
ConsList |
An immutable proper cons lists. |
Iter |
Functions
cons |
Prepend a value to a list. |