# 第3章 列表編程
| 翻譯: | 連城 |
|-----|-----|
這一章研究對列表的處理。列表是用于存儲可變數量的元素的結構。列表的寫法以“[”開頭以“]”結尾。列表的元素以逗號分隔。例如，[E1,E2,E3,...]指代包含元素E1,E2,E3,...的列表。
標記[E1,E2,E3,...,En|Variable]，其中n ≥ 1，用于表示前n個元素為E1,E2,E3,...,En其余部分由Variable指代的列表。當n=1時，列表的形式為[H|T]；這個形式的出現頻率非常高，通常將H稱為列表的**頭部**，而T為列表的**尾部**。
本章我們將討論如何處理**真**列表；即尾部為空列表[]的列表。
應該記住在處理**固定數目**的元素時總是應該使用元組tuple。元組所占的存儲空間僅是列表的一半并且訪問也更迅速。在需要處理可變數目個元素時才應該使用列表。
### 用于列表處理的BIF
一些內置函數可用于列表與其他數據類型間的互相轉換。主要的BIF包括：
atom_to_list(A)
> > 將原子式A轉換為一個ASCII字符列表。
> 如：atom_to_list(hello)?[104,101,108,108,111][[1]](#)。
float_to_list(F)
> > 將浮點數F轉換為一個ASCII字符列表。
> 如：float_to_list(1.5)?[49,46,53,48,48,...,48]。
integer_to_list(I)
> > 將整數I轉換為一個ASCII字符列表。
> 如：integer_to_list(1245)?[[49,50,52,53]。
list_to_atom(L)
> > 將ASCII字符列表L轉換為一個原子式。
> 如：list_to_atom([119,111,114,108,100])?world。
list_to_float(L)
> > 將ASCII字符列表L轉換為一個浮點數。
> 如：list_to_float([51,46,49,52,49,53,57])?3.14159。
list_to_integer(L)
> > 將ASCII字符列表L轉換為一個整數。
> 如：list_to_integer([49,50,51,52])?1234。
hd(L)
> > 返回列表L的第一個元素。
> 如：hd([a,b,c,d])?a。
tl(L)
> > 返回列表L的尾部。
> 如：tl([a,b,c,d])?[b,c,d]。
length(L)
> > 返回列表L的長度。
> 如：length([a,b,c,d])?4。
有兩個BIF tuple_to_list/1和list_to_tuple/1將放在第??章討論。還有一些列表處理相關的BIF，如list_to_pid(AsciiList)、pid_to_list(Pid)。這些將在附錄B中描述。
### 常用列表處理函數
以下各小節給出了一些簡單列表處理函數的使用示例。這里所描述的所有函數都包含在標準Erlang發行版的lists模塊中（細節參見附錄C）。
### member
member(X,L)在X是列表L的元素時返回true，否則返回false。
~~~
member(X, [X|_]) -> true;
member(X, [_|T]) -> member(X, T);
member(X, []) -> false.
~~~
member的第一個子句匹配的是X為列表的第一個元素的情況，這種情況下member返回true。如果第一個子句不匹配，則第二個子句將匹配第二個參數是非空列表的情況，這種情況下模式[_|T]匹配一個非空列表并將T綁定到列表的尾部，然后以原來的X及列表的尾部T遞歸調用member。member前兩個子句就是在說當X是列表的**第一個**元素（頭部），或它被包含在列表的剩余部分（尾部）中時，X就是該列表的一個成員。member的第三個子句是說X不可能是空列表[]的成員，并因此返回false。
我們將member的求值過程列舉如下：
~~~
> 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
~~~
### append
append(A,B)連接兩個列表A和B。
~~~
append([H|L1], L2) -> [H|append(L1, L2)];
append([], L) -> L.
~~~
append的第二個子句再明白不過了——將任意列表L追加至空列表之后仍得到L。
第一個子句給出了追加一個非空列表到另一個列表之后的規則。因此，對于：
~~~
append([a,b,c], [d,e,f])
~~~
其求值結果為：
~~~
[a | append([b,c], [d,e,f])]
~~~
那么append([b,c],[d,e,f])的值又是多少呢？它（當然）是[b,c,d,e,f]，因此[a|append([b,c],[d,e,f])]的值就是[a|append([b,c],[d,e,f])]，這也是[a,b,c,d,e,f]的另一種寫法。
append的行為如下：
~~~
> 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]
~~~
### reverse
reverse(L)用于顛倒列表L中的元素順序。
~~~
reverse(L) -> reverse(L, []).
reverse([H|T], Acc) ->
reverse(T, [H|Acc]);
reverse([], Acc) ->
Acc.
~~~
reverse(L)利用一個**輔助**函數reverse/2將最終結果累積到第二個參數中。
調用reverse(L,Acc)時，若L是一個非空列表，則將L的第一個元素移除并**添加**到Acc的頭部。因此對reverse([x,y,z],Acc)的調用將導致reverse([y,z],[x|Acc])的調用。最終reverse/2的第一個參數將歸結為一個空列表，這時reverse/2的第二個子句將被匹配并另函數結束。
整個過程如下：
~~~
> 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]
~~~
### delete_all
delete_all(X,L)用于刪除列表L中出現的所有X。
~~~
delete_all(X, [X|T]) ->
delete_all(X, T);
delete_all(X, [Y|T]) ->
[Y | delete_all(X, T)];
delete_all(_, []) ->
[].
~~~
delete_all所使用的遞歸模式與member和append類似。
delete_all的第一個子句在要刪除的元素出現在列表的頭部時匹配。
### 示例
在以下章節中我們將給出一些稍微復雜一些的列表處理函數的使用示例。
### 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]
~~~
### 列表的常用遞歸模式
盡管一個典型的程序往往會使用很多不同的函數來操作列表，但大多數列表處理函數都是由少數幾種模式演變而來。大部分列表處理函數無非就是在干著這些事情：
- 在一個列表中尋找一個元素，并在找到時做些事情。
- 對輸入列表的每個元素做些事情并構造一個與其結構相同的輸出列表。
- 在遇到列表中的第*n*個元素時做些事情。
- 對列表進行掃描，并構造一個或一組與原列表相關的新列表。
我們將以此對其進行討論。
### 搜索列表元素
給定以下遞歸模式：
~~~
search(X, [X|T]) ->
... do something ...
...;
search(X, [_|T]) ->
search(X, T);
search(X, []) ->
... didn't find it ...
~~~
第一種情況匹配的是找到了我們所感興趣的項的情形。第二種情況在列表的頭部不是我們所感興趣的項時匹配，這時將接著處理列表的尾部。最后一種情況匹配的是列表元素耗盡的情形。 將以上代碼與member/2的代碼（第??節）作個比較，我們可以看到我們不過是把... do something ...換成了true，把... didn't find it ...換成了false。
構建同構列表 有時我們會想構造一個形如輸入列表的列表，但同時又要對輸入列表的每個元素做些操作。這時可以這么寫：
~~~
isomorphic([X|T]) ->
[something(X)|isomorphic(T)];
isomorphic([]) ->
[].
~~~
然后，比如我們想寫一個將給定列表中的所有元素翻倍的函數，我們就可以這么寫：
~~~
double([H|T]) ->
[2 * H | double(T)];
double([]) ->
[].
~~~
于是便有：
~~~
> lists1:double([1,7,3,9,12]).
[2,14,6,18,24]
~~~
事實上這種手法只能作用于列表的**最上層**，因此如果我們想遍歷列表的所有層次，我們就得將函數定義修改如下：
~~~
double([H|T]) when integer(H)->
[2 * H | double(T)];
double([H|T]) when list(H) ->
[double(H) | double(T)];
double([]) ->
[].
~~~
后一個版本就可以成功遍歷深層的嵌套列表了：
~~~
> lists1:double([1,2,[3,4],[5,[6,12],3]]).
[2,4,[6,8],[10,[12,24],6]]
~~~
### 計數
我們常常要使用到計數器，以便對一個列表的第*n*個元素做些動作：
~~~
count(Terminal, L) ->
... do something ...;
count(N, [_|L]) ->
count(N-1, L).
~~~
則返回列表中第*n*個元素（假設其存在）的函數可以寫成：
~~~
nth(1, [H|T]) ->
H;
nth(N, [_|T]) ->
nth(N - 1, T).
~~~
這種遞減至一個終止條件的計數方式往往要由于遞增計數。為了說明這一點，考慮同樣是返回第*n*個元素但是采用遞增計數的函數nth1：
~~~
nth1(N, L) ->
nth1(1, N, L).
nth1(Max, Max, [H|_]) ->
H;
nth1(N, Max, [_|T]) ->
nth1(N+1, Max, T).
~~~
這種做法需要一個額外的參數和一個輔助函數。
### 收集列表元素
現在我們希望對一個列表中的元素做些動作，生成一個或一組新的列表。對應的模式如下：
~~~
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.
~~~
在這里我們引入了一個多出一個參數的輔助函數，多出的這個參數用于存儲最終要被返回給調用方的列表。
借助這樣一種模式，舉個例子，我們可以寫這樣的一個函數：計算輸入列表的所有偶元素的平方并刪除所有奇元素：
~~~
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.
~~~
于是有：
~~~
> lists:funny([1,2,3,4,5,6])
[36,16,4]
~~~
注意在這種情況下結果列表中的元素的順序與原列表中對應元素的順序是相反的。
在遞歸過程中使用累加列表來構造結果經常是一種推薦的做法。這樣可以編寫出運行時只適用常數空間的**扁平**的代碼（細節參見第??節）。
### 函數式參數
將函數名作為參數傳遞給另一個函數是一種很有用的抽象特定函數行為的方法。本節將給出兩個使用這種編程技術的示例。
### map
函數map(Func,List)返回一個列表L，其中的元素由函數Func依次作用于列表List的各個元素得到。
~~~
map(Func, [H|T]) ->
[apply(F, [H])|map(Func, T)];
map(Func, []) ->
[].
> lists:map({math,factorial}, [1,2,3,4,5,6,7,8]).
[1,2,6,24,120,720,5040,40320]
~~~
### filter
函數filter(Pred,List)對列表List中的元素進行過濾，僅保留令Pred的值為true的元素。這里的Pred是一個返回true或false的函數。
~~~
filter(Pred, [H|T]) ->
case apply(Pred,[H]) of
true ->
[H|filter(Pred, T)];
false ->
filter(Pred, T)
end;
filter(Pred, []) ->
[].
~~~
假設函數math:even/1在參數為偶數時返回true，否則返回fale，則：
~~~
> lists:filter({math,even}, [1,2,3,4,5,6,7,8,9,10]).
[2,4,6,8,10]
~~~
腳注
| [[1]](#) | 標記Lhs?Rhs代表對Lhs求值的結果為Rhs。 |
|-----|-----|
