Lists and recursion

A list is a head and a tail

A list is either empty, written [], or it is one element followed by another list. The pattern [H | T] says exactly that: H is the first element and T is the rest. [1, 2, 3] is 1 followed by [2, 3], which is 2 followed by [3], which is 3 followed by [].

Lists are written with commas for convenience, but the pipe is the real structure. That is why [H | T] is the pattern that every list function is built from, and why taking the first element costs nothing while reaching the thousandth costs a walk.

A list may hold values of any kind, mixed freely: numbers, atoms, strings, tuples, other lists. Length is not part of the value, so adding to the front with the pipe gives a new list and leaves the old one untouched.

Recursion is the loop

Erlang has no for and no while, and it does not need them. A function that walks a list has two clauses: one for [] that states the answer for nothing at all, and one for [H | T] that does something with H and calls itself on T. Each call is smaller than the last, so the walk must end.

The empty clause is the base case and it is not decoration. Without it the recursion would run out of list and then fail with a function clause error, because no clause would match [].

The shape of the answer is decided in the [H | T] clause: adding H to the result for T gives a total; putting 1 + in front of it gives a count; wrapping it in a list gives a new list of the same length. Learn to see the two clauses and most list code becomes readable at a glance.

Where this is heading

Writing your own recursion is worth doing once, because every list function in the standard library is the same two clauses underneath. The next few chapters use the library versions for everyday work and keep hand-written recursion for the shapes the library does not cover.

Two clauses, three walks

-module(prog).
-export([main/1]).

main(_) ->
    io:format("~p~n", [total([1, 2, 3, 4])]),
    io:format("~p~n", [count([a, b, c])]),
    io:format("~p~n", [first_two([10, 20, 30])]).

total([]) -> 0;
total([H | T]) -> H + total(T).

count([]) -> 0;
count([_ | T]) -> 1 + count(T).

first_two([A, B | _]) -> {A, B};
first_two(_) -> none.

Carrying an answer as you walk

The two-clause shape is enough to walk a list, but the answer can be built in two different ways. The first chapter’s total waits for the tail to answer and then adds the head, so the additions happen on the way back out. An accumulator does the work on the way in: a second argument carries the total so far, and the empty clause simply returns it.

Both produce the same number. The accumulator version uses less stack on a long list, because the recursive call is the last thing the clause does and the runtime can reuse the frame. That last-call position is what “tail recursion” means, and it is why library functions are written this way.

The direction of the walk shows in the result

Prepending is cheap and appending is not, so a function that builds a list with [H | Acc] produces it in reverse order. If the answer should read in the original order, either prepend the head to the result of walking the tail, or build reversed and finish with lists:reverse.

This is not a detail to memorise separately for every function. Look at where the new element goes in the recursive clause and you can predict the order before running anything. The base case then tells you what the answer is for an empty list, which is usually 0, [], or the accumulator itself.

Try these next

• Write product/2 with an accumulator starting at 1 and check it on [2, 3, 4].
• Build a list of squares with [H * H | Acc], then reverse it and compare the orders.
• Write a function that keeps only the atoms in a mixed list, using two clauses and an accumulator.