Heads and Tails

When we program with lists in conventional languages, we treat them as things to be iterated, meaning that it seems natural to loop over them. So, why do we have a chapter on lists and recursion? Because if we look at the problem in the right way, recursion is a perfect tool for processing lists.

Heads and tails

Earlier, we said a list may either be empty or consist of a head and a tail. The head contains a value and the tail is itself a list. This is a recursive definition. We’ll represent the empty list like this: [ ]. Let’s imagine we could represent the split between the head and the tail using a pipe character: |. The single-element list we normally write as [ 3 ] can be written as the value 3 joined to the empty list: [3|[]].

Let’s look at the list [2, 3]. The head is 2, and the tail is the single-element list containing 3. So, we could write [2,3] as [2 | [3|[]]].

Processing a list

We can construct a list from a value and a list, which become the head and tail of the new list, respectively.

So, why talk about lists after we talk about modules and functions? Because lists and recursive functions go together like fish and chips. Let’s look at finding the length of a list.

• The length of an empty list is 0.

• The length of a list is 1 + the length of the list’s tail.