Ruslan’s Blog

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.