List (abstract data type)

Implementation of the list data structure may provide some or all of the following operations as low level primitives: • Create an empty list • Test for the list being empty • Prepend an item to the list • Append an item at the list's end • get the first or the last item of a list • get the remainder of the list past its first or last item • get an item by index of its position in a list • create a list containing a single given item • create a list containing given items • append two lists • map, flatmap, filter, reduce, etc. ==Implementations==

Lists are typically implemented either as linked lists (either singly or doubly linked) or as arrays, usually variable length or dynamic arrays. The standard way of implementing lists, originating with the programming language Lisp, is to have each element of the list contain both its value and a pointer indicating the location of the next element in the list. This results in either a linked list or a tree, depending on whether the list has nested sublists. Some older Lisp implementations (such as the Lisp implementation of the Symbolics 3600) also supported "compressed lists" (using CDR coding) which had a special internal representation (invisible to the user). Lists can be manipulated using iteration or recursion. The former is often preferred in imperative programming languages, while the latter is the norm in functional languages. 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. ==Programming language support==

Some languages do not offer a list data structure, but offer the use of associative arrays or some kind of table to emulate lists. For example, Lua provides tables. Although Lua stores lists that have numerical indices as arrays internally, they still appear as dictionaries. In Lisp, lists are the fundamental data type and can represent both program code and data. In most dialects, the list of the first three prime numbers could be written as (list 2 3 5). In several dialects of Lisp, including Scheme, a list is a collection of pairs, consisting of a value and a pointer to the next pair (or null value), making a singly linked list. ==Applications==

Unlike in an array, a list can expand and shrink. In computing, lists are easier to implement than sets. 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. Sorting the list speeds up determining if a given item is already in the set, but in order to ensure the order, it requires more time to add a new entry to the list. In efficient implementations, however, sets are implemented using self-balancing binary search trees or hash tables, rather than a list. Lists also form the basis for other abstract data types including the queue, the stack, and their variations. ==Abstract definition==

The abstract list type L with elements of some type E (a monomorphic list) is defined by the following functions: :nil: () → L :cons: E × L → L :first: L → E :rest: L → L with the axioms :first (cons (e, l)) = e :rest (cons (e, l)) = l for any element e and any list l. It is implicit that :cons (e, l) ≠ l :cons (e, l) ≠ e :cons (e1, l1) = cons (e2, l2) if e1 = e2 and l1 = l2 Note that first (nil ()) and rest (nil ()) are not defined. These axioms are equivalent to those of the abstract stack data type. In type theory, the above definition is more simply regarded as an inductive type defined in terms of constructors: nil and cons. 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 monad The list type forms a monad with the following functions (using E* rather than L to represent monomorphic lists with elements of type E): :\text{return}\colon A \to A^{*} = a \mapsto \text{cons} \, a \, \text{nil} :\text{bind}\colon A^{*} \to (A \to B^{*}) \to B^{*} = l \mapsto f \mapsto \begin{cases} \text{nil} & \text{if} \ l = \text{nil}\\ \text{append} \, (f \, a) \, (\text{bind} \, l' \, f) & \text{if} \ l = \text{cons} \, a \, l' \end{cases} where append is defined as: :\text{append}\colon A^{*} \to A^{*} \to A^{*} = l_1 \mapsto l_2 \mapsto \begin{cases} l_2 & \text{if} \ l_1 = \text{nil} \\ \text{cons} \, a \, (\text{append} \, l_1' \, l_2) & \text{if} \ l_1 = \text{cons} \, a \, l_1' \end{cases} Alternatively, the monad may be defined in terms of operations return, fmap and join, with: :\text{fmap} \colon (A \to B) \to (A^{*} \to B^{*}) = f \mapsto l \mapsto \begin{cases} \text{nil} & \text{if} \ l = \text{nil}\\ \text{cons} \, (f \, a) (\text{fmap} f \, l') & \text{if} \ l = \text{cons} \, a \, l' \end{cases} :\text{join} \colon {A^{*}}^{*} \to A^{*} = l \mapsto \begin{cases} \text{nil} & \text{if} \ l = \text{nil}\\ \text{append} \, a \, (\text{join} \, l') & \text{if} \ l = \text{cons} \, a \, l' \end{cases} Note that fmap, join, append and bind are well-defined, since they're applied to progressively deeper arguments at each recursive call. The list type is an additive monad, with nil as the monadic zero and append as monadic sum. Lists form a monoid under the append operation. The identity element of the monoid is the empty list, nil. In fact, this is the free monoid over the set of list elements. ==See also==