Previous parts: Intro, Part I, Part II, Part III and Part IV
List comprehensions.
List comprehensions is very familiar topic for Python programmer. It’s a syntactic sugar which provides a succinct notation for producing elements in list.
Erlang:
[Expr || Qualifier1,...,QualifierN]
Expr - is an arbitrary expression
Qualifier is either a generator or a filter.
A generator is of form Pattern <- ListExpr where ListExpr evaluates to a list of terms.
A filter expression should evaluate to true or false.
1> [X || X <- [1,2,3,4,5,6], X > 3].
[4,5,6]
This is read as: list of X such that X is taken from list [1,2,3,4,5,6] and X is greater than 3.
In foregoing example: X <- [1,2,3,4,5,6] is a generator and X > 3 is a filter.
Several filters can be combined:
2> [X || X <- [1,a,2,3,b,4,5,6], X > 3].
[a,b,4,5,6]
3> [X || X <- [1,a,2,3,b,4,5,6], integer(X), X > 3].
[4,5,6]
Generator part may act as a filter in list comprehension:
4> [X || {X, a} <- [{1, a}, {2, b}, {3, a}, erlang]].
[1,3]
Generators can be combined too in list comprehensions. This is the Cartesian product of two lists:
5> [{X, Y} || X <- [1, 2, 3], Y <- [a, b]].
[{1,a},{1,b},{2,a},{2,b},{3,a},{3,b}]
This is how elegantly quicksort algorithm is solved with the help of list comprehensions in Erlang:
-module(sort).
-export([qsort/1]).
qsort([]) -> [];
qsort([Pivot|Tail]) ->
qsort([X || X <- Tail, X < Pivot])
++ [Pivot] ++
qsort([X || X <- Tail, X >= Pivot]).
Compile and run:
6> c("/home/alienoid/dev/erlang/sort", [{outdir, "/home/alienoid/dev/erlang/"}]).
{ok,sort}
7> sort:qsort([7, 5, 9, 3, 6]).
[3,5,6,7,9]
Usage of list comprehensions instead of some higher-order functions:
8> lists:map(fun(X) -> X*2 end, [1, 2, 3]).
[2,4,6]
9> [X*2 || X <- [1, 2, 3]].
[2,4,6]
10> lists:filter(fun(X) -> X rem 2 == 0 end, [1, 2, 3, 4]).
[2,4]
11> [X || X <- [1, 2, 3, 4], X rem 2 == 0].
[2,4]
Python:
[expression for expr1 in seq1 if cond1
for expr2 in seq2 if cond2
for exprN in seqN if condN]
this actually transforms to:
for expr1 in seq1:
if not cond1:
continue
for expr2 in seq2:
if not cond2:
continue
for exprN in seqN:
if not condN:
continue
So in Python Cartesian product of two lists [1, 2, 3 ] and ['a', 'b'] will look like:
>>> [(x, y) for x in [1, 2, 3] for y in ['a', 'b']]
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')]
Variable bindings and scope rules in List Comprehensions:
Current Python 2.x “leaks” loop variable into surrounding scope. This should be solved in Python 3.0
>>> x
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'x' is not defined
>>> vlist = [x for x in 'abc']
>>> vlist
['a', 'b', 'c']
>>> x
'c'
To avoid leaking loop variable into surrounding scope we can use generator expression which doesn’t “leak”:
>>> vlist = list(x for x in 'abc')
>>> vlist
['a', 'b', 'c']
>>> x
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'x' is not defined
Erlang has following scope rules for variables in list comprehensions(from Erlang manual):
- 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
So, Erlang doesn’t “leak” variables:
1> [X || X <- [1, 2, 3]].
[1,2,3]
2> X.
** 1: variable 'X' is unbound **
Be careful, sometimes you need to move some pattern matching operations into filter:
-module(listcomp).
-export([select/2]).
%% This select produces following warning during compilation:
%% Warning: variable 'X' shadowed in generate
select(X, List) ->
[Y || {X, Y} <- List].
The function doesn’t produce desired result:
1> listcomp:select(b, [{b, 1}, {c, 2}, {b, 3}]).
[1,2,3]
So we modify generator and move pattern matching operation into filter to achieve what we need:
-module(listcomp).
-export([select/2]).
%% Moving X from pattern matching into filter
select(X, List) ->
[Y || {X1, Y} <- List, X == X1].
2> listcomp:select(b, [{b, 1}, {c, 2}, {b, 3}]).
[1,3]
As you saw, while different in syntax, both languages provide valuable language construct which allows to write shorter and more elegant programs.
Posted by Ruslan Spivak
