3  列表推导

3.1  简单示例

本节从一个简单的示例开始，展示了生成器和过滤器

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

解释如下：所有 X 的列表，其中 X 取自列表 [1,2,a,...] 且 X 大于 3。

符号 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}]

3.2  快速排序

众所周知的快速排序算法可以写成如下形式

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

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

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

按如下方式排序的列表

• 列表中的第一个元素被隔离，并且列表被分成两个子列表。
• 第一个子列表包含所有小于列表中第一个元素的元素。
• 第二个子列表包含所有大于或等于列表中第一个元素的元素。
• 然后对子列表进行排序，并将结果合并。

3.3  排列

以下示例生成列表中所有元素的排列

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

3.4  勾股数

勾股数是整数集 {A,B,C}，满足 A**2 + B**2 = C**2。

函数 pyth(N) 生成所有满足 A**2 + B**2 = C**2 且三边之和等于或小于 N 的整数集 {A,B,C} 的列表

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

3.5  使用列表推导简化

例如，列表推导可以用来简化 lists.erl 中的一些函数

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

3.6  列表推导中的变量绑定

出现在列表推导中的变量的作用域规则如下

• 所有出现在生成器模式中的变量都被认为是“新”变量。
• 在列表推导之前定义的任何变量，如果在过滤器中使用，将具有在列表推导之前的值。
• 变量不能从列表推导中导出。

作为这些规则的示例，假设你想编写函数 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, ...]
    ...