List (abstract data type)

In computer science, a list or sequence is a collection of items that are finite in number and in a particular order.

An instance of a list is a computer representation of the mathematical concept of a tuple or finite sequence.

Lists can be implemented as self-balancing binary search trees holding index-value pairs, providing equal-time access to any element (e.g. all residing in the fringe, and internal nodes storing the right-most child's index, used to guide the search), taking the time logarithmic in the list's size, but as long as it doesn't change much will provide the illusion of random access and enable swap, prefix and append operations in logarithmic time as well.

A finite set in the mathematical sense can be realized as a list with additional restrictions; that is, duplicate elements are disallowed and order is irrelevant.

Lists also form the basis for other abstract data types including the queue, the stack, and their variations.

In algebraic terms, this can be represented as the transformation 1 + E × L → L. first and rest are then obtained by pattern matching on the cons constructor and separately handling the nil case.

The list type forms a monad with the following functions (using E* rather than L to represent monomorphic lists with elements of type E): where append is defined as: Alternatively, the monad may be defined in terms of operations return, fmap and join, with: Note that fmap, join, append and bind are well-defined, since they're applied to progressively deeper arguments at each recursive call.