An ordered sequence of values.
A list is a sequence of values with the following properties:
- The list maybe empty.
- The values in the list are ordered.
- The same value may occur more than once.
- The list has a size that is equal to the number of values in the list.
- Each element in a list L has an index. The first element has index 0. The last element has index
Formally, a list can be defined as follows. Given the domains
ELEM (elements) and
LIST (lists) and the functions:
nil : -> LIST
cons: ELEM x LIST -> LIST
head: LIST -> ELEM
tail: LIST -> LIST
cons are so-called constructor functions that define the values in
LIST. They can be paraphrased as:
- The empty list
nilis an element of
eis an element of
lis an element of LIST, then
cons(e, l)is also an element in
head (take the first element) and
tail (take the remainder of a list)
are defined functions characterized by the axioms:
head(cons(e, l)) = e
tail(cons(e, l)) = l
tail(nil) are left undefined (and usually correspond to a runtime error in a programming language).
In Rascal, lists are surrounded by brackets
] and the elements are separated by commas.
Each list has a type of the form
list[T], where T is the smallest common type of all list elements.
Read the description of lists and their operators
and of library functions on lists.
Lists in Daily Life
- A line of people waiting for the super market checkout or bus stop. credit
- The wagons of a train.
- The Top 100 Music Charts. credit
- Twitter users ordered according to number of followers.
- A to do list.
Lists in computer science
- The locations in a computer memory.
- The list of processes that use most cpu time.
- The list of procedures that are called by a given procedure.
Lists in Rascal
- The empty list:
. Its type is
- A list of integers:
[3, 1, 4]. Its type is
- A list of mixed-type values:
[3, "a", 4]. Its type is