檢視原始碼 列表解析

簡單範例

本節從一個簡單的範例開始，展示一個產生器和一個過濾器

> [X || X <- [1,2,a,3,4,b,5,6], X > 3].
[a,4,b,5,6]

讀作：從列表 [1,2,a,...] 中取出 X，並且 X 大於 3 的所有 X 的列表。

標記 X <- [1,2,a,...] 是一個產生器，而表達式 X > 3 是一個過濾器。

可以添加額外的過濾器 is_integer(X)，將結果限制為整數

> [X || X <- [1,2,a,3,4,b,5,6], is_integer(X), X > 3].
[4,5,6]

產生器可以組合使用。例如，兩個列表的笛卡爾積可以寫成如下

> [{X, Y} || X <- [1,2,3], Y <- [a,b]].
[{1,a},{1,b},{2,a},{2,b},{3,a},{3,b}]

快速排序

著名的快速排序常式可以寫成如下

sort([]) -> [];
sort([_] = L) -> L;
sort([Pivot|T]) ->
    sort([ X || X <- T, X < Pivot]) ++
    [Pivot] ++
    sort([ X || X <- T, X >= Pivot]).

表達式 [X || X <- T, X < Pivot] 是 T 中所有小於 Pivot 的元素的列表。

[X || X <- T, X >= Pivot] 是 T 中所有大於或等於 Pivot 的元素的列表。

使用上述演算法，列表的排序方式如下

  • 包含零個或一個元素的列表是平凡排序的。
  • 對於包含一個以上元素的列表
    1. 列表中的第一個元素被隔離為樞紐元素。
    2. 剩餘的列表被劃分為兩個子列表，使得
    • 第一個子列表包含所有小於樞紐元素的元素。
    • 第二個子列表包含所有大於或等於樞紐元素的元素。
    1. 子列表通過相同的演算法遞迴排序，並且結果被組合，產生一個包含以下元素的列表
    • 來自第一個子列表的所有元素，即所有小於樞紐元素的元素，按照排序順序排列。
    • 樞紐元素。
    • 來自第二個子列表的所有元素，即所有大於或等於樞紐元素的元素，按照排序順序排列。

注意

雖然如上所示的排序演算法是一個很好的範例，用於說明帶有過濾器的列表解析，但對於實際用例，lists 模組包含以更有效的方式實現的排序函數。

排列

以下範例產生列表中元素的所有排列

perms([]) -> [[]];
perms(L)  -> [[H|T] || H <- L, T <- perms(L--[H])].

這從 L 中以所有可能的方式取出 H。結果是所有列表 [H|T] 的集合，其中 T 是 L 的所有可能排列的集合，並移除 H。

> perms([b,u,g]).
[[b,u,g],[b,g,u],[u,b,g],[u,g,b],[g,b,u],[g,u,b]]

畢氏三元數

畢氏三元數是整數集合 {A,B,C}，使得 A**2 + B**2 = C**2。

函數 pyth(N) 生成所有整數 {A,B,C} 的列表，使得 A**2 + B**2 = C**2，且邊的和等於或小於 N

pyth(N) ->
    [ {A,B,C} ||
        A <- lists:seq(1,N),
        B <- lists:seq(1,N),
        C <- lists:seq(1,N),
        A+B+C =< N,
        A*A+B*B == C*C
    ].
> pyth(3).
[].
> pyth(11).
[].
> pyth(12).
[{3,4,5},{4,3,5}]
> pyth(50).
[{3,4,5},
 {4,3,5},
 {5,12,13},
 {6,8,10},
 {8,6,10},
 {8,15,17},
 {9,12,15},
 {12,5,13},
 {12,9,15},
 {12,16,20},
 {15,8,17},
 {16,12,20}]

以下程式碼減少了搜尋空間，效率更高

pyth1(N) ->
   [{A,B,C} ||
       A <- lists:seq(1,N-2),
       B <- lists:seq(A+1,N-1),
       C <- lists:seq(B+1,N),
       A+B+C =< N,
       A*A+B*B == C*C ].

使用列表解析簡化

例如，列表解析可以用於簡化 lists.erl 中的一些函數

append(L)   ->  [X || L1 <- L, X <- L1].
map(Fun, L) -> [Fun(X) || X <- L].
filter(Pred, L) -> [X || X <- L, Pred(X)].

列表解析中的變數綁定

列表解析中出現的變數的範圍規則如下

  • 在產生器模式中出現的所有變數都假定為「新的」變數。
  • 在列表解析之前定義的，並且在過濾器中使用的任何變數，都具有在列表解析之前的值。
  • 變數無法從列表解析中匯出。

作為這些規則的範例，假設您想編寫函數 select，它從元組列表中選擇某些元素。假設您編寫 select(X, L) -> [Y || {X, Y} <- L].，目的是從 L 中提取所有第一個項目是 X 的元組。

編譯此程式碼會產生以下診斷訊息

./FileName.erl:Line: Warning: variable 'X' shadowed in generate

此診斷警告模式中的變數 X 與函數頭中出現的變數 X 不同。

評估 select 會產生以下結果

> select(b,[{a,1},{b,2},{c,3},{b,7}]).
[1,2,3,7]

這不是想要的效果。為了達到預期的效果，select 必須寫成如下

select(X, L) ->  [Y || {X1, Y} <- L, X == X1].

產生器現在包含未綁定的變數，並且測試已移至過濾器中。

現在可以按預期工作了

> select(b,[{a,1},{b,2},{c,3},{b,7}]).
[2,7]

另請注意，產生器模式中的變數將會遮蔽先前產生器模式中綁定同名的變數。例如

> [{X,Y} || X <- [1,2,3], X=Y <- [a,b,c]].
[{a,a},{b,b},{c,c},{a,a},{b,b},{c,c},{a,a},{b,b},{c,c}]

將變數導入列表解析的規則的一個結果是，某些模式匹配操作必須移至過濾器中，而不能直接在產生器中編寫。

為了說明這一點，請不要如下編寫

f(...) ->
    Y = ...
    [ Expression || PatternInvolving Y  <- Expr, ...]
    ...

請改為如下編寫

f(...) ->
    Y = ...
    [ Expression || PatternInvolving Y1  <- Expr, Y == Y1, ...]
    ...