3 List Comprehensions

3.1 Simple Examples

This section starts with a simple example, showing a generator and a filter:

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

This is read as follows: The list of X such that X is taken from the list [1,2,a,...] and X is greater than 3.

The notation X <- [1,2,a,...] is a generator and the expression X > 3 is a filter.

An additional filter, is_integer(X), can be added to restrict the result to integers:

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

Generators can be combined. For example, the Cartesian product of two lists can be written as follows:

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

3.2 Quick Sort

The well-known quick sort routine can be written as follows:

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

The expression [X || X <- T, X < Pivot] is the list of all elements in T that are less than Pivot.

[X || X <- T, X >= Pivot] is the list of all elements in T that are greater than or equal to Pivot.

A list sorted as follows:

The first element in the list is isolated and the list is split into two sublists.
The first sublist contains all elements that are smaller than the first element in the list.
The second sublist contains all elements that are greater than, or equal to, the first element in the list.
Then the sublists are sorted and the results are combined.

3.3 Permutations

The following example generates all permutations of the elements in a list:

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

This takes H from L in all possible ways. The result is the set of all lists [H|T], where T is the set of all possible permutations of L, with H removed:

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

3.4 Pythagorean Triplets

Pythagorean triplets are sets of integers {A,B,C} such that A**2 + B**2 = C**2.

The function pyth(N) generates a list of all integers {A,B,C} such that A**2 + B**2 = C**2 and where the sum of the sides is equal to, or less than, 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}]

The following code reduces the search space and is more efficient:

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 Simplifications With List Comprehensions

As an example, list comprehensions can be used to simplify some of the functions in 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 Variable Bindings in List Comprehensions

The scope rules for variables that occur in list comprehensions are as follows:

All variables that occur in a generator pattern are assumed to be "fresh" variables.
Any variables that are defined before the list comprehension, and that are used in filters, have the values they had before the list comprehension.
Variables cannot be exported from a list comprehension.

As an example of these rules, suppose you want to write the function select, which selects certain elements from a list of tuples. Suppose you write select(X, L) -> [Y || {X, Y} <- L]. with the intention of extracting all tuples from L, where the first item is X.

Compiling this gives the following diagnostic:

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

This diagnostic warns that the variable X in the pattern is not the same as the variable X that occurs in the function head.

Evaluating select gives the following result:

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

This is not the wanted result. To achieve the desired effect, select must be written as follows:

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

The generator now contains unbound variables and the test has been moved into the filter.

This now works as expected:

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

Also note that a variable in a generator pattern will shadow a variable with the same name bound in a previous generator pattern. For example:

> [{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}]

A consequence of the rules for importing variables into a list comprehensions is that certain pattern matching operations must be moved into the filters and cannot be written directly in the generators.

To illustrate this, do not write as follows:

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

Instead, write as follows:

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

Chapters