3.7 Lists

The type list is builtin or predefined by the language. This type could be easily defined by the programmer, see Exercise 4, except that the language allows the representation of lists in a special notation which is more agile than that that would be available to the programmer. The following statement defines important concepts of a list:

A list is either nil or it is a cons consisting of an element, referred to as the head of the list, and another list, referred to as the tail of the list.

The nil list is denoted by “[]”, which is read “nil”. A cons list, with head $h$ and tail $t$ is denoted by “$h$:$t$”. The infix operator “:”, which is read “cons”, is right associative with precedence 5. A list can also be denoted by enumerating its elements, e.g., “[u,v,w]” is a list containing three elements, “u”, “v” and “w”, i.e., it is just another notation for “u:v:w:[]”. The number of elements is arbitrary. The elements are enclosed in brackets and separated by commas.

The following functions concatenate two lists and reverse a list, respectively. The “Prelude” defines the first one as the infix operator “++” and the second one, much more efficiently, as the operation “reverse”.

Several ad hoc notations available for lists are described in Sections 4.2.3 and 4.2.4.

A key advantage of these special notations for lists is a reduction of the number of parentheses needed to represent list expressions in a program. This claim can be easily verified by comparing the builtin notation with the ordinary notation which was the subject of Exercise 4.