The Empty List, Cons, Head and Tail

There is a special list called the Empty List. Type []; into Hope. Hope responds with
>> nil : list alpha
nil is another word for the empty list. Its type is list alpha. Here alpha means any type. It could be a list of integers or a list of bools or a list of anything else.

There is a special operator on lists called `cons' written ::. Try

>: 1::[2];
Hope responds with
>> [1, 2] : list num

Now try

>: 1::[1,1,1,1];
Hope responds with
>> [1, 1, 1, 1, 1] : list num


Now try

>: true::[false,true];
Hope responds with
>> [true, false, true] : list bool;

So cons takes an element and list and makes a new list who head is the element and who tail is the list. i.e.

head: list alpha -> alpha;
head (x::m) <= x;

tail: list alpha -> list alpha;
tail (x::m) <= m;

Sebastian Danicic BSc MSc PhD (Reader in Computer Science)
Dept of Computing, Goldsmiths, University of London, London SE14 6NW
Last updated 2010-12-29