Lists in functional programming revision notes

Core representation

A list can be considered as a concatenation of a head and a tail. The head is an element of the list, normally the first element. The tail is the remainder of the list and is itself a list. For example, the list [4, 3, 5] has head 4 and tail [3, 5]. The list [] is the empty list and has no head or tail.

Required operations

• Return the head: obtain the first element of a non-empty list.
• Return the tail: obtain all elements after the first element. The result is a list.
• Test for an empty list: determine whether a list contains no elements.
• Return the length: count the number of elements in the list. The length of [] is 0.
• Construct an empty list: use [].
• Prepend an item: place an item at the beginning of a list. If items = [3, 5], prepending 4 gives [4, 3, 5].
• Append an item: place an item at the end of a list. If items = [4, 3], appending 5 gives [4, 3, 5].

Python examples

python items = [4, 3, 5] head = items[0] # return head: 4 tail = items[1:] # return tail: [3, 5] is_empty = (items == []) # test for empty list size = len(items) # return length: 3 empty = [] # construct an empty list prepended = [2] + items # prepend: [2, 4, 3, 5] appended = items + [6] # append: [4, 3, 5, 6]

Common errors

Do not confuse the head with the tail: the head is one element, whereas the tail is a list. Do not treat the tail as the final element; it is everything after the head. A head or tail operation must not be applied as though the empty list had a first element. Also distinguish prepend, which changes the beginning of the list, from append, which changes the end.