In the following sections we give some slightly more complex examples of list processing functions.

### 3.3.1. `sort`

Program 3.1 is a variant of the well-known quicksort algorithm. `sort(X)`

returns a sorted list of the elements of the list `X`

.

```
-module(sort).
-export([sort/1]).
sort([]) -> [];
sort([Pivot|Rest]) ->
{Smaller, Bigger} = split(Pivot, Rest),
lists:append(sort(Smaller), [Pivot|sort(Bigger)]).
split(Pivot, L) ->
split(Pivot, L, [], []).
split(Pivot, [], Smaller, Bigger) ->
{Smaller,Bigger};
split(Pivot, [H|T], Smaller, Bigger) when H < Pivot ->
split(Pivot, T, [H|Smaller], Bigger);
split(Pivot, [H|T], Smaller, Bigger) when H >= Pivot ->
split(Pivot, T, Smaller, [H|Bigger]).
```

The first element of the list to be sorted is used as a pivot. The original list is partitioned into two lists `Smaller`

and `Bigger`

: all the elements in `Smaller`

are less than `Pivot`

and all the elements in `Bigger`

are greater than or equal to `Pivot`

. The lists `Smaller`

and `Bigger`

are then sorted and the results combined.

The function `split(Pivot, L)`

returns the tuple `{Smaller,Bigger}`

, where all the elements in `Bigger`

are greater than or equal to `Pivot`

and all the elements in `Smaller`

are less than `Pivot`

. `split(Pivot, L)`

works by calling the auxiliary function `split(Pivot, L, Smaller, Bigger)`

. Two accumulators, `Smaller`

and `Bigger`

, are used to store the elements in `L`

which are smaller than and greater than or equal to `Pivot`

, respectively. The code in `split/4`

is very similar to that in `reverse/2`

except that two accumulators are used instead of one. For example:

```
> lists:split(7,[2,1,4,23,6,8,43,9,3]).
{[3,6,4,1,2],[9,43,8,23]}
```

If we call `sort([7,2,1,4,23,6,8,43,9,3])`

, the first thing which happens is that `split/2`

is called with pivot `7`

. This results in two lists: `[3,6,4,1,2]`

whose elements are less than the pivot, `7`

, and `[9,43,8,23]`

whose elements are greater than or equal to the pivot.

Assuming that `sort`

works then `sort([3,6,4,1,2]) ⇒ [1,2,3,4,6]`

and `sort([9,43,8,23]) ⇒ [8,9,23,43]`

. Finally, the sorted lists are appended with the call:

```
> append([1,2,3,4,6], [7 | [8,9,23,43]]).
[1,2,3,4,6,7,8,9,23,43]
```

With a little ingenuity the call to `append`

can be removed, as in the following:

```
qsort(X) ->
qsort(X, []).
%% qsort(A,B)
%% Inputs:
%% A = unsorted List
%% B = sorted list where all elements in B
%% are greater than any element in A
%% Returns
%% sort(A) appended to B
qsort([Pivot|Rest], Tail) ->
{Smaller,Bigger} = split(Pivot, Rest),
qsort(Smaller, [Pivot|qsort(Bigger,Tail)]);
qsort([], Tail) ->
Tail.
```

We can compare the performance of this with the first version of sort by using the BIF `statistics/1`

(see appendix, which provides information about the performance of the system). If we compile and run the code fragment:

```
...
statistics(reductions),
lists:sort([2,1,4,23,6,7,8,43,9,4,7]),
{_, Reductions1} = statistics(reductions),
lists:qsort([2,1,4,23,6,7,8,43,9,4,7]),
{_, Reductions2} = statistics(reductions),
...
```

We can find out how many reductions (function calls) it took to evaluate the call the `sort`

and `qsort`

functions. In our example `sort`

took `93`

reductions and `qsort`

took `74`

, a `20`

percent improvement.

### 3.3.2. Sets

Program 3.2 is a simple collection of set manipulation functions. The obvious way to represent sets in Erlang is as an unordered list of elements without duplication.

The set manipulation functions are as follows:

`new()`

- Returns an empty set.
`add_element(X, S)`

- Adds an element
`X`

to the set`S`

and returns a new set. `del_element(X, S)`

- Deletes the element
`X`

from the set`S`

and returns a new set. `is_element(X, S)`

- Returns true if the element
`X`

is contained in the set`S`

, otherwise`false`

. `is_empty(S)`

- Returns true if the set
`S`

is empty otherwise`false`

. `union(S1, S2)`

- Returns the union of the sets
`S1`

and`S2`

, i.e. the set of all elements which are contained in either`S1`

or`S2`

. `intersection(S1, S2)`

- Returns the intersection of the sets
`S1`

and`S2`

, i.e. the set of all elements which are contained in both`S1`

and`S2`

.

Strictly speaking, we should not say new returns an empty set but rather `new`

returns a *representation* of an empty set. If we represent the sets as lists, then the set operations can be written as follows:

```
-module(sets).
-export([new/0, add_element/2, del_element/2,
is_element/2, is_empty/1, union/2, intersection/2]).
new() -> [].
add_element(X, Set) ->
case is_element(X, Set) of
true -> Set;
false -> [X|Set]
end.
del_element(X, [X|T]) -> T;
del_element(X, [Y|T]) -> [Y|del_element(X,T)];
del_element(_, []) -> [].
is_element(H, [H|_]) -> true;
is_element(H, [_|Set]) -> is_element(H, Set);
is_element(_, []) -> false.
is_empty([]) -> true;
is_empty(_) -> false.
union([H|T], Set) -> union(T, add_element(H, Set));
union([], Set) -> Set.
intersection(S1, S2) -> intersection(S1, S2, []).
intersection([], _, S) -> S;
intersection([H|T], S1, S) ->
case is_element(H,S1) of
true -> intersection(T, S1, [H|S]);
false -> intersection(T, S1, S)
end.
```

Running the code in Program 3.2:

```
> S1 = sets:new().
[]
> S2 = sets:add_element(a, S1).
[a]
> S3 = sets:add_element(b, S2).
[b,a]
> sets:is_element(a, S3).
true
> sets:is_element(1, S2).
false
> T1 = sets:new().
[]
> T2 = sets:add_element(a, T1).
[a]
> T3 = sets:add_element(x, T2).
[x,a]
> sets:intersection(S3, T3).
[a]
> sets:union(S3,T3).
[b,x,a]
```

This implementation is not particularly efficient, but it is sufficiently simple to be (hopefully) correct. At a later stage it could be replaced by a more efficient version.

### 3.3.3. Prime numbers

In our final example (Program 3.3) we see how a list of prime numbers can be generated using the sieve of *Eratosthenes algorithm*.

```
-module(siv).
-compile(export_all).
range(N, N) ->
[N];
range(Min, Max) ->
[Min | range(Min+1, Max)].
remove_multiples(N, [H|T]) when H rem N == 0 ->
remove_multiples(N, T);
remove_multiples(N, [H|T]) ->
[H | remove_multiples(N, T)];
remove_multiples(_, []) ->
[].
sieve([H|T]) ->
[H | sieve(remove_multiples(H, T))];
sieve([]) ->
[].
primes(Max) ->
sieve(range(2, Max)).
```

Note that in Program 3.3 we use the compiler annotation `-compile(export_all)`

– this implicitly exports all functions in the module so they can be called without giving explicit export declarations.

`range(Min, Max)`

returns a list of the integers between `Min`

and `Max`

. `remove_multiples(N, L)`

removes all multiples of `N`

from the list `L`

:

```
> siv:range(1,15).
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
> siv:remove_multiples(3,[1,2,3,4,5,6,7,8,9,10]).
[1,2,4,5,7,8,10]
```

`sieve(L)`

retains the head of the list `L`

and recursively removes all multiples of the head of the list from the sieved tail of the list:

```
> siv:primes(25).
[2,3,5,7,11,13,17,19,23]
```