3 List Comprehensions
List comprehensions are a feature of many modern functional programming languages. Subject to certain rules, they provide a succinct notation for generating elements in a list.
List comprehensions are analogous to set comprehensions in Zermelo-Frankel set theory and are called ZF expressions in Miranda and SASL. They are analogous to the
setof
andfindall
predicates in Prolog.List comprehensions are written with the following syntax:
[Expression || Qualifier1, Qualifier2, ...]
Expression
is an arbitrary expression, and eachQualifier
is either a generator or a filter.
- A generator written as
Pattern <- ListExpr
.ListExpr
must be an expression which evaluates to a list of terms.- A filter is either a predicate or a boolean expression. A predicate is a function which returns
true
orfalse
.3.1 Examples of List Comprehensions
We start with a simple example:
> [X || X <- [1,2,a,3,4,b,5,6], X > 3]. [a,4,b,5,6]This should be 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 expressionX > 3
is a filter.An additional filter can be added in order to restrict the result to integers:
> [X || X <- [1,2,a,3,4,b,5,6], 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.1.1 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 inT
, which are less thanPivot
.
[X || X <- T, X >= Pivot]
is the list of all elements inT
, which are greater or equal toPivot
.To sort a list, we isolate the first element in the list and split the list into two sub-lists. The first sub-list contains all elements which are smaller than the first element in the list, the second contains all elements which are greater than or equal to the first element in the list. We then sort the sub-lists and combine the results.
3.1.2 Permutations
The following example generates all permutations of the elements in a list:
perms([]) -> [[]]; perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].We take take
H
fromL
in all possible ways. The result is the set of all lists[H|T]
, whereT
is the set of all possible permutations ofL
withH
removed.> perms([b,u,g]). [[b,u,g],[b,g,u],[u,b,g],[u,g,b],[g,b,u],[g,u,b]]3.1.3 Pythagorean Triplets
Pythagorean triplets are sets of integers
{A,B,C}
such thatA**2 + B**2 = C**2
.The function
pyth(N)
generates a list of all integers{A,B,C}
such thatA**2 + B**2 = C**2
and where the sum of the sides is less thanN
.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), B <- lists:seq(1,N-A+1), C <- lists:seq(1,N-A-B+2), A+B+C =< N, A*A+B*B == C*C ].3.1.4 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.2 Variable Bindings in List Comprehensions
The scope rules for variables which occur in list comprehensions are as follows:
- all variables which occur in a generator pattern are assumed to be "fresh" variables
- any variables which are defined before the list comprehension and which are used in filters have the values they had before the list comprehension
- no variables may be exported from a list comprehension.
As an example of these rules, suppose we want to write the function
select
, which selects certain elements from a list of tuples. We might writeselect(X, L) -> [Y || {X, Y} <- L].
with the intention of extracting all tuples fromL
where the first item isX
.Compiling this yields the following diagnostic:
./FileName.erl:Line: Warning: variable 'X' shadowed in generateThis diagnostic warns us that the variable
X
in the pattern is not the same variable as the variableX
which occurs in the function head.Evaluating
select
yields the following result:> select(b,[{a,1},{b,2},{c,3},{b,7}]). [1,2,3,7]This result is not what we wanted. To achieve the desired effect we must write
select
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]One consequence of the rules for importing variables into a list comprehensions is that certain pattern matching operations have to 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, ...] ...