List processing

Lists as a head and a tail, the empty list, prepend and append, and recursion over a list to drive a route there and back.

A13.6Functional programmingA level25 min

At GCSE a list was an array: a row of boxes you reach into by index, readings[3]. Functional languages think of a list differently, as something built up one item at a time, and process it by taking it apart one item at a time. This lesson covers that view of a list, the operations the exam names, and how recursion over a list replaces a loop.

Head and tail

A list is either:

• the empty list, written [], or
• a head followed by a tail: the head is the first element, and the tail is the list of everything after it.

The head is an element; the tail is a list (possibly empty). So the list [31, 51, 15] is 31 put in front of the list [51, 15], which is 51 in front of [15], which is 15 in front of []. Haskell writes "put in front of" with a colon, so these are the same list:

[31, 51, 15]
31 : [51, 15]
31 : (51 : (15 : []))

The list operations

These are the operations the exam asks you to describe and apply, in Haskell and in Python with tuples, which are immutable like Haskell's lists:

Two points catch people out. head and tail of the empty list are errors: there is no first element to return. And Haskell's ++ joins two lists, so to append a single item you put it in a list of its own, [5].

def head(xs): return xs[0]
def tail(xs): return xs[1:]
def is_empty(xs): return xs == ()
def prepend(x, xs): return (x,) + xs
def append(xs, x): return xs + (x,)

readings = (31, 51, 15)
print(head(readings), tail(readings), is_empty(readings), is_empty(()))
print(prepend(0, readings), append(readings, 99))
print(readings)                     # unchanged: every operation made a new tuple
print(head(tail(tail(readings))))   # the third item, reached by head and tail

Run this in the simulator

Recursion over a list

Because a list is "empty, or a head and a tail", a function over a list has two cases, and the second calls the function again on the tail:

• Base case: the empty list. Return the answer for no items.
• General case: combine the head with the result for the tail.

Here is the length of a list, written the functional way:

len' :: [a] -> Int
len' []     = 0
len' (x:xs) = 1 + len' xs

The pattern (x:xs) matches a list that has a head, naming the head x and the tail xs. len' [7,8,9] works out as 1 + len' [8,9] = 1 + (1 + len' [9]) = 1 + (1 + (1 + len' [])) = 1 + 1 + 1 + 0 = 3. The name has a ' because Haskell already has a length.

The same in Python, and a sum:

def head(xs): return xs[0]
def tail(xs): return xs[1:]
def is_empty(xs): return xs == ()

def length(xs):
    if is_empty(xs):
        return 0
    return 1 + length(tail(xs))

def total(xs):
    if is_empty(xs):
        return 0
    return head(xs) + total(tail(xs))

print(length((7, 8, 9)), total((7, 8, 9)), length(()))

Run this in the simulator

Every list function in a functional language is built this way, including map, filter and the folds. map in Haskell is two lines:

map f []     = []
map f (x:xs) = f x : map f xs

Apply f to the head, and prepend the result to map f of the tail.

Why prepend is cheap and append is not

Haskell's lists are linked lists (lesson A3.4). Prepending makes one new node that points at the existing list, which is shared, not copied, so it takes the same time however long the list is. Appending has to rebuild every node up to the end, because the old last node cannot be changed to point somewhere new: the data is immutable. So a functional program builds a list by prepending, and reverses it at the end if the order matters. (Python's tuples are arrays, not linked lists, so there both copy the whole tuple.)

A route as a list

BugBot's route is a list of moves. Driving it is list processing: carry out the head, then drive the tail.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def head(xs): return xs[0]
def tail(xs): return xs[1:]
def is_empty(xs): return xs == ()

def drive(route):
    if is_empty(route):
        print("route finished")
        return
    letter, amount = head(route)
    print(letter, amount)
    if letter == "F":
        forward(50, distance=amount)
    else:
        turn_right(30, angle=amount)
    drive(tail(route))

drive((("F", 20), ("R", 90), ("F", 15)))

Run this in the simulator

Task: there and back

Drive a route, then come back along it, using only list operations and recursion. There must be no for or while, no len, and no reversed or [::-1] anywhere.

• Write head(xs), tail(xs), is_empty(xs), prepend(x, xs) and append(xs, x) for tuples, as in the table above.
• length(xs) returns the number of items in the tuple xs, by recursion.
• reverse(xs) returns a new tuple with the items of xs in the opposite order, by recursion: the reverse of a list is the reverse of its tail, with its head appended.
• invert(move) takes a move, a tuple (letter, amount) where the letter is "F", "B", "L" or "R" and the amount a whole number, and returns the move that undoes it: "F" and "B" swap, "L" and "R" swap, and the amount stays the same.
• drive(route) carries out a tuple of moves by recursion. For each move, in order, it prints the letter and amount separated by a space, such as F 30, then drives forward or backward at speed 50 or turns left or right at speed 30.

Using ROUTE from the starter, print length: <n> and head: <the first move> (Python's own printing of the tuple, such as ('F', 30)). Then drive ROUTE, and then drive back to the start along the route undone: the inverted moves of the reversed route.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

ROUTE = (("F", 30), ("R", 90), ("F", 20), ("L", 45), ("F", 10))

for move in ROUTE:
    print(move[0], move[1])
    forward(50, distance=move[1])

Challenges

1. Write last(xs), the final item of a list, using only head, tail and is_empty.
2. Write take(n, xs), the first n items, in Haskell style with two equations, then in Python.
3. Rewrite reverse so it builds the answer by prepending, carrying a second parameter for the answer so far. Why would a Haskell programmer prefer it?