Lists: heads, tails and helpers

One pattern for every list

A list is written with square brackets: [coffee, tea, milk]. Behind the scenes it is a chain of pairs that ends in the empty list, which is why a single pattern is enough to take it apart. [H | T] means the first item and the rest of the list.

The vertical bar is the split. [H | T] matches any list with at least one item, and a helper that also handles the empty list covers every list there is.

A pattern can name more than the first item. [First, Second | Rest] matches a list with at least two items, binding the first two and leaving the rest. The vertical bar appears once, and everything to its right is still a list. A pattern with no bar, such as [A, B], matches exactly two items and fails on a longer list.

Helpers you write yourself

This sandbox is the core engine only, so the familiar list helpers are not built in. There is no member, no append and no length, and nothing to import that would add them. Each one is a handful of lines, and writing them is the quickest way to understand lists.

The helper that finds an item walks down the list until the item matches. The helper that counts walks down and adds one on the way back out. Both are two clauses: one for the empty list, one for the head-and-tail case.

A helper can be used in more than one direction. contains(tea, [coffee, tea, milk]) is a test, while contains(X, [coffee, tea, milk]) enumerates the items one at a time. The same clauses serve both because the pattern does not care which positions are bound; the search fills in whatever is free.

The tail is a list, the head is an item

[H | T] is not a special list syntax with two slots; it is the pair every list is built from. H is one item, T is the rest of the list — which is itself a list, and may be []. That is why a helper calls itself on T and why the clause for [] is the only one that stops the walk.

A one-item list has a head and an empty tail: [tea] is the same term as [tea | []], and a two-item list is [coffee | [tea]], which prints as [coffee, tea]. Lists are not arrays: there is no index and no constant-time access, so reaching the third item means walking past the first two. The helper is a walk, not a loop with a counter.

Underneath, a list is a chain of two-argument terms ending in the atom []. [coffee, tea] is a pair whose first argument is coffee and whose second argument is another pair, [tea], and the square-bracket form is only a readable way to write that chain. That is why the head-and-tail pattern works on every list: it is matching the chain itself, not a special list object.

A worked trace

Trace contains(tea, [coffee, tea, milk]). The first clause matches only if the head is tea; coffee is not, so it fails. The second clause matches with H as coffee and T as [tea, milk], then calls contains(tea, [tea, milk]). Now the first clause matches, because the head is tea, and the whole goal succeeds. The milk is never visited.

The same trace explains the cost. Finding an item near the front is quick; finding one near the end walks past every earlier cell. There is no index to jump to, and no way to ask for the third item without walking the first two. That is the trade a linked structure makes: cheap to take apart at the front, expensive to reach into the middle.

Joining two lists

% Joining two lists, one clause for each shape.
join([], L, L).
join([H | T], L, [H | R]) :-
    join(T, L, R).

main :-
    join([1, 2], [3, 4], R),
    write('joined '), write(R), nl,
    join(Front, [3, 4], [1, 2, 3, 4]),
    write('front '), write(Front), nl.
:- initialization(main).

Try these next

• Write last/2, which finds the only item whose tail is empty.
• Write sum/2 and check it on an empty list.
• Trace contains(tea, [coffee, tea, milk]) by hand, clause by clause.