Lists¶
A list is a sequence of values of the same type. Lists are
constructed via the list constructor function, e.g., list[1, 2,
3] creates a list of three integers. An empty list is created via
list[] or Nil.
The time to access a value via nth is proportional to the length
of the list. The first value of a list can be accessed in constant
time, using the head function.
The map, fold and filter second-order functions described
in this section implement common functional programming patterns. To
execute some statements for each element in a list, use a foreach
loop (see The foreach loop).
Datatypes and constructors¶
A list is defined either as the empty list (Nil) or as a value
a followed by another list l (Cons(a, l)):
data List<A> = Nil | Cons(A head, List<A> tail);
Literal lists of arbitrary length can be written using a special
function list. In the following example, l1 and l2
contain the same elements:
List<Int> l1 = list[1, 2, 3];
List<Int> l2 = Cons(1, Cons(2, Cons(3, Nil)));
Functions¶
head¶
Returns the head of a list.
head(list[1, 2, 3])
// => 1
tail¶
Returns the tail (rest) of a list.
tail(list[1, 2, 3])
// => list[2, 3]
length¶
Returns the length of a list. The length of Nil is 0.
- ::
length(list[1, 2, 3]) // => 3
isEmpty¶
Checks if a list is empty. Returns True for Nil, False
otherwise.
isEmpty(list[1, 2, 3])
// => False
isEmpty(list[])
// => True
nth¶
Returns the n-th element of a list. Returns the head of l for
n``=0, returns the last element of ``l when n is
length(l)-1.
It is an error if n is equal to or larger than length(l).
nth(list[1, 2, 3], 2)
// => 3
without¶
Returns a fresh list where all occurrences of a have been removed.
without(list[1, 2, 3, 3, 5], 3)
// => list[1, 2, 5]
concatenate¶
Returns a list containing all elements of list list1 followed by
all elements of list list2.
concatenate(list[1, 2, 3], list[4, 5])
// => list[1, 2, 3, 4, 5]
appendright¶
Returns a list containing all elements of list l followed by the
element p in the last position.
appendright(list[1, 2], 3)
// => list[1, 2, 3]
reverse¶
Returns a list containing all elements of l in reverse order.
reverse(list[1, 2, 3])
// => list[3, 2, 1]
copy¶
Returns a list of length n containing p n times.
copy(-1, 4)
// => list[-1, -1, -1, -1]
map¶
Applies a function to each element of a list, returning a list of
results in the same order. The function fn must take an argument
of type A and return a value of type B.
map((Int x) => x + 1)(list[1, 2, 3])
// => list[2, 3, 4]
filter¶
Returns a list containing only the elements in the given list for
which the given predicate returns True. The function
predicate must take an argument of type T and return a Boolean
value.
filter((Int x) => x < 4)(list[1, 2, 3, 4, 5])
// => list[1, 2, 3]
foldl¶
Accumulates a value starting with init and applying accumulate
from left to right to current accumulator value and each element. The
function accumulate must take two arguments: the first of type
A (the type of the list) and the second of type B (the
accumulator and result type), and return a value of type B.
foldl((Int x, String res) => res + toString(x))(list[1, 2, 3], "")
// => "123"
foldr¶
Accumulates a value starting with init and applying accumulate
from right to left to each element and current accumulator value. The
function accumulate must take two arguments: the first of type
A (the type of the list) and the second of type B (the
accumulator and result type), and return a value of type B.
foldl((Int x, String res) => res + toString(x))(list[1, 2, 3], "")
// => "321"
range¶
Returns a list of integers ranging from the first to the second
argument, inclusive. If lower is equal to upper, returns a
list of one element; if lower is larger than upper, returns an
empty list.
range(2, 5)
// => list[2, 3, 4, 5]
