示例

示例

在以下章节中我们将给出一些稍微复杂一些的列表处理函数的使用示例。

sort

程序3.1是著名的快速排序的一个变体。sort(X)对列表X的元素排序，将结果放入一个新列表并将之返回。

程序3.1

-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]).

此处选取列表的第一个元素为中轴。元列表被分为两个列表Smaller和Bigger：Smaller的所有元素都小于中轴Pivot而Bigger的所有元素都大于等于Pivot。之后，再对列表Smaller和Bigger分别排序并将结果合并。

函数split({Pivot,L})返回元组{Smaller,Bigger}，其中所有Bigger中的元素都大于等于Pivot而所有Smaller中的元素都小于Pivot。split(Pivot,L)通过调用一个辅助函数split(Pivot,L,Smaller,Bigger)完成任务。两个累加列表，Smaller和Bigger分别用于存储L中小于和大于等于Pivot的元素。split/4的代码与reverse/2非常相像，只是多用了一个累加列表。例如：

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

如果我们调用sort([7,2,1,4,23,6,8,43,9,3])，首先就会以7为中轴来调用split/2。这将产生两个列表：所有元素都小于中轴7的[3,6,4,1,2]，以及所有元素都大于等于中轴的[9,43,8,23]。

假设sort工作正常，则sort([3,6,4,1,2])⇒[1,2,3,4,6]而sort([9,43,8,23])⇒[8,9,23,43]。最后，排好序的列表被拼装在一起：

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

再动一点脑筋，都append的调用也可以省掉，如下所示：

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.

我们可以利用BIFstatistics/1（用于提供系统性能相关的信息，参见附录??）将之与第一版的sort做一个对比。如果我们编译并执行以下代码片段：

...
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),
...

我们可以得知sort和qsort的归约（函数调用）次数。在我们的示例中sort花费93次归约，而qsort花费74次，提升了百分之二十。

集合

程序3.2是一组简单的集合操作函数。在Erlang中表示集合的最直白的方法就是采用一个不包含重复元素的无序列表。

集合操作函数如下：

new()

返回一个空集合。

add_element(X,S)

返回将元素X并入集合S 产生的新集合。

del_element(X,S)

返回从集合S中删去元素X的新集合。

is_element(X,S)

当元素X在集合S中时返回true，否则返回false。

is_empty(S)

当集合S为空集时返回true，否则返回false。

union(S1,S2)

返回集合S1和S2的并集，即包含了S1或S2所有元素的集合。

intersection(S1,S2)

返回集合S1和S2的交集，即仅包含既包含于S1又包含于S2的元素的集合。

严格地说，我们并不能说new返回了一个空集，而应该说new返回了一个空集的表示 。如果我们将集合表示为列表，则以上的集合操作可以编写如下：

程序3.2

-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.

运行程序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]
10> sets:union(S3,T3).
[b,x,a]

这个实现并不十分高效，但足够简单以保证其正确性（但愿如此）。今后还可以将之替换为一套更高效的实现。

素数

在我们的最后一个例子（程序3.3）中，我们将来看看如何使用埃拉托色尼筛法 来生成一张素数表。

程序 3.3

-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)).

注意在程序3.3中我们使用了编译器标注-compile(export_all)——这将隐式地导出该模块中的所有函数，于是我们无须显式地给出导出申明便可以调用这些函数。

range(Min,Max)返回一个包含从Min到Max的所有整数的列表。

remove_multiples(N,L)从列表L删除中N的倍数：

> 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)保留列表L的头部，对于尾部的列表，则再递归地删除其头部的所有倍数：

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