Lists in functional programming

Overview

Recall questions on the head and tail of a list, the empty list, what happens when the head of an empty list is requested, and the seven basic list operations.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   How is a list represented as a concatenation of a head and a tail?

   Model answer

   Any non-empty list is treated as a single element stuck on the front of another list. That leading element is the head and everything behind it is the tail, and the tail is itself a list, which is what makes the idea recursive. Haskell writes the split with a colon, so [4, 3, 5] is 4:[3, 5] — the head is 4 and the tail is [3, 5]. Peel again and the tail becomes 3:[5], then 5:[], and finally the empty list, which has no head at all and is where a recursion over a list stops.

2. 2

   Is the head of a list an element or a list? What about the tail?

   Model answer

   The head is an element of the list — a single item, not a list containing that item. The tail is a list — the remainder of the list once the head has been removed. So for [4, 3, 5] the head is 4 and the tail is [3, 5], not 4 and 3. Confusing the two is the commonest error here, and it matters because an operation expecting a list cannot be given an element, or the other way round.

3. 3

   For the list [8], what are the head and the tail?

   Model answer

   The head is the element 8 and the tail is the empty list, written []. The tail is still a list even though it has nothing in it, which is consistent with the rule that the tail of any list is a list.

4. 4

   Can a list be empty, and how is the empty list written?

   Model answer

   Yes, a list can be empty. In Haskell the empty list is written []. It is a perfectly good list; it simply has no elements, so it has no head and no tail. It is what remains after the last element has been removed, and it is the value a construction of a list starts from.

5. 5

   What happens if you ask for the head of an empty list, and why?

   Model answer

   It is an error, because there is no first element for the operation to return. The same applies to asking for the tail of an empty list. This is why any function that works its way through a list must test for the empty list before taking the head, and it is why the test for an empty list is one of the basic operations.

6. 6

   List the seven basic list operations.

   Model answer

   Three of them inspect a list without changing it: take its head, take its tail, and report its length. One asks a question about it: is it empty? The remaining three build lists: make an empty one to start from, join an item onto the front, and join an item onto the end. The two joining operations differ in cost as well as position — putting an item on the front is cheap because the existing list becomes the tail untouched, whereas putting one on the end means working the whole way down first.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.