Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 36 ยท Data Structures

List Comprehensions

Build lists concisely with Erlang list comprehensions: generators, filters, multiple generators, pattern generators, binary comprehensions and map comprehensions.

A list comprehension builds a new list from existing ones by describing what each element looks like and which source elements to use. It does the job of map, filter and nested loops in one short expression. If you know set-builder notation from math, the shape will feel familiar: "the set of X squared, for X in this set, where X is even".

Basic form

ERLANG
[Expression || Generator, Filter, ...]

The part before || is the output expression. After it come qualifiers: generators (Pattern <- List) and filters (boolean expressions).

ERLANG
1> [X * X || X <- [1, 2, 3, 4]].
[1,4,9,16]
2> [X || X <- [1, 2, 3, 4, 5, 6], X rem 2 =:= 0].
[2,4,6]
3> [X * 2 || X <- lists:seq(1, 10), X > 5].
[12,14,16,18,20]

Read the first line as: "for each X taken from the list, produce X * X." The second adds a filter, so only even numbers pass. A comprehension replaces a lists:map with a fun, or a lists:filter, often with clearer code. Compare:

ERLANG
lists:map(fun(X) -> X * X end, lists:filter(fun(X) -> X rem 2 =:= 0 end, L))

with

ERLANG
[X * X || X <- L, X rem 2 =:= 0]

Pattern generators

The left side of <- is a pattern. Elements that do not match are skipped silently, which gives an easy filter-and-extract in one step:

ERLANG
1> Pets = [{cat, 4}, {dog, 7}, {fish, 1}, {cat, 9}].
2> [Age || {cat, Age} <- Pets].
[4,9]
3> [Name || {Name, Age} <- Pets, Age > 3].
[cat,dog,cat]
4> [{Name, Age * 2} || {Name, Age} <- Pets].
[{cat,8},{dog,14},{fish,2},{cat,18}]

In line 2 only tuples starting with cat match, and Age is bound for each one. The same trick works to pull the ok values out of results:

ERLANG
Values = [V || {ok, V} <- Results].

Multiple generators

Several generators produce a combination of all elements, with the last generator varying fastest:

ERLANG
1> [{X, Y} || X <- [1, 2, 3], Y <- [a, b]].
[{1,a},{1,b},{2,a},{2,b},{3,a},{3,b}]
2> [X + Y || X <- [1, 2, 3], Y <- [10, 20]].
[11,21,12,22,13,23]

A filter can use variables from earlier generators, for instance to generate Pythagorean triples:

ERLANG
1> [{A, B, C} || A <- lists:seq(1, 20),
1>               B <- lists:seq(A, 20),
1>               C <- lists:seq(B, 20),
1>               A * A + B * B =:= C * C].
[{3,4,5},{5,12,13},{6,8,10},{8,15,17},{9,12,15},{12,16,20}]

Variables inside comprehensions

A variable bound in a generator is local to the comprehension and does not leak out; it shadows any variable of the same name outside (with a compiler warning). Variables from outside can be read:

ERLANG
1> Limit = 3.
2> [X || X <- [1, 2, 3, 4, 5], X < Limit].
[1,2]

Quick examples

Flatten one level:

ERLANG
[Y || X <- [[1, 2], [3], [4, 5]], Y <- X].       % [1,2,3,4,5]

Transpose pairs, build a lookup, simple quicksort:

ERLANG
qsort([]) -> [];
qsort([Pivot | Rest]) ->
    qsort([X || X <- Rest, X < Pivot]) ++
    [Pivot] ++
    qsort([X || X <- Rest, X >= Pivot]).
ERLANG
1> qsort([3, 6, 1, 8, 2, 9, 2]).
[1,2,2,3,6,8,9]

This quicksort is not the fastest, but it shows why comprehensions are loved: the algorithm reads like its definition.

Binary comprehensions

Use << ... >> to build or consume binaries:

ERLANG
1> << <<(X * 2)>> || <<X>> <= <<1, 2, 3>> >>.
<<2,4,6>>
2> [X || <<X>> <= <<"abc">>].
"abc"

The generator for binaries is <= (not <-). Here every byte X of the input binary is doubled in the output binary. Binaries are covered in the binaries lesson.

Map comprehensions (OTP 26+)

Recent OTP releases also support comprehensions over maps, written with =>:

ERLANG
1> #{K => V * 2 || K := V <- #{a => 1, b => 2}}.
#{a => 2,b => 4}

The generator K := V <- Map iterates over the key/value pairs. See maps for the data type.

When not to use them

For side effects only, use lists:foreach/2, not a comprehension; the comprehension builds a list you will throw away. For aggregation (sum, count, max) use lists:foldl/3; comprehensions return lists. And keep each one short: when it grows past three qualifiers, split it into helper functions with names.

Stand-ins in JavaScript

JavaScript's flatMap, filter and map mirror the shape. These samples are not Erlang.

JS Stand-in: generators and filters (JavaScript, not Erlang)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

JS Stand-in: Pythagorean triples and quicksort (JavaScript, not Erlang)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does [X * 2 || X <- [1, 2, 3]] return?

    Each X is taken from the list and replaced by X * 2.
  2. 2. What happens to list elements that do not match a pattern generator such as {cat, Age} <- Pets?

    Non-matching elements are silently skipped, which makes pattern generators a filter.
  3. 3. In [{X, Y} || X <- [1,2], Y <- [a,b]], which generator varies fastest?

    The last generator loops innermost, so the result is [{1,a},{1,b},{2,a},{2,b}].
  4. 4. Which generator arrow is used to consume a binary?

    Binary generators use <=, for example <<X>> <= Binary.

Summary

  • [Expr || Generator, Filter, ...] builds a list from generators (Pattern <- List) and filters.
  • Patterns in generators skip elements that do not match.
  • Several generators produce all combinations; the last one varies fastest.
  • Binary comprehensions use <<...>> with <=; map comprehensions use K := V <- Map (OTP 26+).
  • Use foreach for side effects and foldl for aggregation.

Next: Tuples and Records