3.4. Common Patterns of Recursion on Lists

Although a typical program may use many different functions which operate on lists, most list processing functions are variations on one of a small number of themes. Most list processing functions involve elements of:

• Searching for an element in a list and doing something when the element is found.
• Building an output list where the output list has the same shape as the input list but where something has been done to each element in the list.
• Doing something when we have encountered the nth item in a list.
• Scanning the list and building a new list or lists which are in some way related to the original list.

We will consider each of these in turn.

3.4.1. Searching for elements in a list

Here we have the following pattern of recursion:

search(X, [X|T]) ->
    ... do something ...
    ...;

search(X, [_|T]) ->
    search(X, T);
search(X, []) ->
    ... didn’t find it ...

The first case matches when we have located the item of interest. The second case matches when the head of the list does not match the item of interest, in which case the tail of the list is processed. The final case matches when the elements in the list have been exhausted.

Comparing the above with the code for member/2 we see we replace the code for ... do something ... by true and the code for ... didn’t find it ... by false.

3.4.2. Building an isomorphic list

We may wish to build a list which has the same shape as the input list, but where we have performed some operation to each element on the list. This we could express as follows:

isomorphic([X|T]) ->
    [something(X)|isomorphic(T)];

isomorphic([]) ->
    [].

So, for example, if we wanted to write a function which doubled each element of a list we could write:

double([H|T]) ->
    [2 * H | double(T)];
double([]) ->
    [].

So for example:

> lists1:double([1,7,3,9,12]).
[2,14,6,18,24]

This actually only works on the top level of a list, so if we wanted to traverse all levels of the list, we would have to change the definition to:

double([H|T]) when integer(H) ->
    [2 * H | double(T)];
double([H|T]) when list(H) ->
    [double(H) |double(T)];
double([]) ->
    [].

The latter version successfully traverses deep lists:

> lists1:double([1,2,[3,4],[5,[6,12],3]]).
[2,4,[6,8],[10,[12,24],6]]

3.4.3. Counting

We often need counters so that we can do something when we hit the nth element in a list:

count(Terminal, L) ->
        ... do something ...;
count(N, [_|L]) ->
        count(N-1, L).

Thus a function to extract the nth element of a list (assuming it exists) can be written:

nth(1, [H|T]) ->
    H;
nth(N, [_|T]) ->
    nth(N - 1, T).

The technique of counting downwards towards some terminal condition is often preferable to counting upwards. To illustrate this consider nth1, which also determines the nth element of a list but this time counting upwards:

nth1(N, L) ->
    nth1(1, N, L).

nth1(Max, Max, [H|_]) ->
    H;
nth1(N, Max, [_|T]) ->
    nth1(N+1, Max, T).

This requires the use of one additional parameter and an auxiliary function.

3.4.4. Collecting elements of a list

Here we wish to do something to elements of a list, producing a new list or lists. The pattern of interest is:

collect(L) ->
    collect(L, []).

collect([H|T], Accumulator) ->
    case pred(H) of
        true ->
            collect(T, [dosomething(H)|Accumulator]);
        false ->
            collect(T, Accumulator)
    end;

collect([], Accumulator) ->
    Accumulator.

Here we introduce an auxiliary function with an additional argument which is used to store the result which will eventually be returned to the calling program.

Using such a schema we could, for example, write a function which returns a list where every even element in the list has been squared and every odd element removed:

funny(L) ->
    funny(L, []).

funny([H|T], Accumulator) ->
    case even(H) of
        true -> funny(T, [H*H|Accumulator]);
        false -> funny(T, Accumulator)
    end;

funny([], Accumulator) ->
    Accumulator.

Thus for example:

> lists:funny([1,2,3,4,5,6])
[36,16,4]

Note that in this case the elements in the resulting list are in the reverse order to those from which they were derived in the original list.

Use of accumulators is often preferable to building the result in the recursion itself. This leads to flat code which executes in constant space.