A list is a container in which the elements are in order
"In order" means, that there's a first element, which has a successor element, which also has a successor element and so on. If the list is finite, there's a last element without a successor. If the list empty, there isn't even a first element. Every element e
together with it's successors is a list of it's own, with e
as the first element. It must be possible to define two operations for the container:
- accessing the first element
- extracting the tail (if any). The tail of a list is the (sub-)list where the first element is the successor of the original first element.
Both operations can be arbitrary complex but must be consistent for all lists. Examples for accessing the first element: indexing at [0]
, using functions like Lisp's car
. Examples for extracting the tail of a list l
: python: tail=l[1:]
, pointer to arrays in C: tail=l+1
, Lisp: function cdr
.
Indexing at i
is not an inherent feature of a list (but of an array), but can be trivially achieved by starting at the first element and taking i
times the tail and then the head thereof.
Lists can be implemented with functions that map integers i
to the i
th element, but only if the language supports higher order functions, because when extracting the tail you have to create a new list-function out of the original list-function. Example (using Haskell syntax): l = join(*)
is the (infinite) list of all square numbers. l 1
is the first element and tail = (.succ) l
is the tail. Both operations (providing 1
as an argument and using (.succ)
) are consistent for all list-functions.
List can be implemented via dictionaries with integers as keys. In Perl, %l = (1 => 1, 2 => 4, 3 => 9)
is a list of the first three square numbers. The first element is accessed via lookup of key 1
and the tail via removing key 1 and re-mapping all remaining key/value pairs accordingly.
Some notes:
- lists as defined above have basically the same features as singly linked lists
- function/dictionaries don't have to use integers as arguments/keys, any ordered type will do, e.g. characters.
- yes, you can also implement finite lists with functions. The list of the first 4 square numbers is (again, using Haskell syntax):
f x|x>0,x<5=x*x|otherwise=undefined
- usually a list requires some method to check for the empty list. For functions you can use a pair (list-function, length) just like C arrays also need a separate length variable or you can introduce a special element
nil
to mark the end of the list.