Erlang for Python programmers: Part V

by Ruslan Spivak on November 16, 2007

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.

If you enjoyed this post why not subscribe via email or my RSS feed and get the latest updates immediately. You can also follow me on GitHub or Twitter.

{ 3 comments… read them below or add one }

Andy Freeman November 16, 2007 at 11:35 AM

Erlang makes it difficult to get values out of list comprehensions. The second rule is especially annoying because non-local variables are the typical mechanism for doing so.

Reply

Dirceu Pereira Tiegs March 12, 2009 at 8:34 PM

Hey, thanks for sharing these quick tutorials, they’re very helpful!

Reply

Ruslan Spivak March 15, 2009 at 11:41 PM

You’re welcome

Reply

Speak your mind

Previous post:

Next post: