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
Vector, which has more efficient
performance characteristics in almost all cases. The
particularly useful as an immutable stack where you only push and
pop items from the front of the list. Beware that it has no
An immutable proper cons lists.
Prepend a value to a list.