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.