3.2. Some Common List Processing Functions

The following sections give some examples of simple list processing functions. All the functions described in this section are contained in the module lists which is contained in the standard Erlang distribution (see Appendix C for more details).

3.2.1. member

member(X, L) returns true if X is an element of the list L, otherwise false.

member(X, [X|_]) -> true;
member(X, [_|T]) -> member(X, T);
member(X, []) -> false.

The first clause in member matches the case where X is the first element of the list, in which case member returns true. If the first clause does not match, then the second clause will match if the second argument of member is a non-empty list, in which case the pattern [_|T] matches a non-empty list and binds T to the tail of the list, and then member is called with the original argument X and the tail of the input list T. The first two clauses of member say that X is a member of a list if it is the first element (head) of the list, or if it is contained in the remainder of the list (tail). The third clause of member states that X cannot be a member of the empty list [] and false is returned.

We illustrate the evaluation of member as follows:

> lists:member(a,[1,2,a,b,c]).
(0)lists:member(a,[1,2,a,b,c])
(1).lists:member(a, [2,a,b,c])
(2)..lists:member(a,[a,b,c])
(2)..true
(1).true
(0)true
true

> lists:member(a,[1,2,3,4]).
(0)lists:member(a, [1,2,3,4])
(1).lists:member(a, [2,3,4])
(2)..lists:member(a, [3,4])
(3)...lists:member(a, [4])
(4)....lists:member(a, [])
(4)....false
(3)...false
(2)..false
(1).false
(0)false
false

3.2.2. append

append(A,B) concatenates the two lists A and B.

append([H|L1], L2) -> [H|append(L1, L2)];
append([], L) -> L.

The second clause of append is the easiest to understand – it says that appending any list L to the empty list just results in L.

The first clause gives a rule for appending a non-empty list to some other list. So, for example:

append([a,b,c], [d,e,f])

reduces to:

[a | append([b,c], [d,e,f])]

But what is the value of append([b,c],[d,e,f])? It is (of course) [b,c,d,e,f], so the value of [a|append([b,c], [d,e,f])] is [a|[b,c,d,e,f]] which is another way of writing [a,b,c,d,e,f].

The behaviour of append is seen as follows:

> lists:append([a,b,c],[d,e,f]).
(0)lists:append([a,b,c],[d,e,f])
(1).lists:append([b,c], [d,e,f])
(2)..lists:append([c],[d,e,f])
(3)...lists:append([], [d,e,f])
(3)...[d,e,f]
(2)..[c,d,e,f]
(1).[b,c,d,e,f]
(0)[a,b,c,d,e,f]
[a,b,c,d,e,f]

3.2.3. reverse

reverse(L) reverses the order of the elements in the list L.

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

reverse([H|T], Acc) ->
    reverse(T, [H|Acc]);
reverse([], Acc) ->
    Acc.

reverse(L) makes use of an auxiliary function reverse/2 which accumulates the final result in its second parameter.

If a call is made to reverse(L, Acc) when L is a non-empty list, then the first element of L is removed from L and added to the head of the list Acc. Thus reverse([x,y,z], Acc) results in a call to reverse([y,z], [x|Acc]). Eventually the first argument to reverse/2 is reduced to the empty list, in which case the second clause of reverse/2 matches and the function terminates.

This can be illustrated as follows:

> lists:reverse([a,b,c,d]).
(0)lists:reverse([a,b,c,d])
(1).lists:reverse([a,b,c,d], [])
(2)..lists:reverse([b,c,d], [a])
(3)...lists:reverse([c,d], [b,a])
(4)....lists:reverse([d], [c,b,a])
(5).....lists:reverse([], [d,c,b,a])
(5).....[d,c,b,a]
(4)....[d,c,b,a]
(3)...[d,c,b,a]
(2)..[d,c,b,a]
(1).[d,c,b,a]
(0)[d,c,b,a]
[d,c,b,a]

3.2.4. delete all

delete_all(X, L) deletes all occurrences of X from the list L.

delete_all(X, [X|T]) ->
    delete_all(X, T);
delete_all(X, [Y|T]) ->
    [Y | delete_all(X, T)];
delete_all(_, []) ->
    [].

The patterns of recursion involved in delete_all are similar to those involved in member and append.

The first clause of delete_all matches when the element to be deleted is at the head of the list being examined.

In the second clause we know that Y is different from X (otherwise the first clause would have matched). We retain the first element of the list being examined Y, and call delete_all on the tail of the list.

The third clause matches when the second parameter of delete_all has been reduced to the empty list.

> lists:delete_all(a,[1,2,a,3,a,4]).
[1,2,3,4]