Skip to main content

List

rascal-0.40.17

Synopsis​

An ordered sequence of values.

Description​

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 size(L)-1.

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

nil and cons are so-called constructor functions that define the values in LIST. They can be paraphrased as:

  • The empty list nil is an element of LIST.
  • If e is an element of ELEM and l is an element of LIST, then cons(e, l) is also an element in LIST.

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

The cases head(nil) and tail(nil) are left undefined (and usually correspond to a runtime error in a programming language).

In Rascal, lists are surrounded by brackets [ and ] 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. queue.pngcredit
  • The wagons of a train.
  • The Top 100 Music Charts. hot100.pngcredit
  • 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 list[void].
  • A list of integers: [3, 1, 4]. Its type is list[int].
  • A list of mixed-type values: [3, "a", 4]. Its type is list[value].