3.列出理解 | 3. List Comprehensions

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是个过滤器。

一个额外的过滤器，integer(X)，以将结果限制为整数：

> [X || X <- [1,2,a,3,4,b,5,6], 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])].

这需要H从L以各种可能的方式。结果是所有列表的集合。[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毕达哥拉斯Triplets

勾股数是整数集的{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 ].

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]

将变量导入列表解析的规则的一个后果是某些模式匹配操作必须移入过滤器，并且不能直接写入生成器。

要说明这一点，请执行不写如下：

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

相反，写如下：

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