Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 57 ยท Types and values

List Comprehensions

Build Haskell lists the way mathematicians write sets: generators, guards, nested generators, let bindings and pattern filters, with examples.

A list comprehension builds a new list out of one or more existing lists. The notation is borrowed from set-builder notation in mathematics: "the squares of all numbers from 1 to 5" becomes [x * x | x <- [1 .. 5]]. Once you can read that line, you can read most comprehensions.

Comprehensions are compact, but they are not magic: each one is shorthand for combinations of map, filter and concatMap, which you will meet in Higher-Order Functions. They are a good first tool for transforming lists, and they show off Haskell's laziness nicely. This lesson assumes you know tuples and lists.

The basic shape

HASKELL
[ expression | qualifier, qualifier, ... ]

Everything left of the bar is the output expression: what each element of the result looks like. Everything right of the bar is a comma-separated list of qualifiers: generators, guards and let bindings. Read it as "the expression, for every combination the qualifiers allow".

HASKELL
[x * x | x <- [1 .. 5]]
-- [1,4,9,16,25]

x <- [1 .. 5] is a generator. It takes each element of the list in turn and names it x. The output expression is then evaluated once per element.

Guards filter

A qualifier that is a plain Bool expression is a guard. Only elements for which every guard is True survive.

HASKELL
[x | x <- [1 .. 10], even x]
-- [2,4,6,8,10]

[x * x | x <- [1 .. 10], odd x, x > 3]
-- [25,49,81]

[c | c <- "Hello World", c `elem` ['A' .. 'Z']]
-- "HW"

The last example shows that a string is a list of characters, so comprehensions work on text too. Guards are evaluated left to right, and later qualifiers can use variables bound by earlier ones.

Three kinds of qualifier

Generator x <- xs takes each element.
Guard A Bool that keeps or drops the element.
let Names a helper value for later parts.

Qualifiers run left to right, and later ones see earlier names.

1 / 2

Several generators: all combinations

With more than one generator you get every combination. The last generator changes fastest, like the inner loop of nested loops.

HASKELL
[(x, y) | x <- [1 .. 3], y <- "ab"]
-- [(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]

A later generator may depend on an earlier one. This lists each pair with x < y once, without repeats:

HASKELL
[(x, y) | x <- [1 .. 4], y <- [x + 1 .. 4]]
-- [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]

The classic demonstration is the search for Pythagorean triples: whole numbers a, b, c with aยฒ + bยฒ = cยฒ.

HASKELL
triples :: Int -> [(Int, Int, Int)]
triples n =
  [ (a, b, c)
  | c <- [1 .. n]
  , b <- [1 .. c]
  , a <- [1 .. b]
  , a * a + b * b == c * c
  ]
-- triples 20 == [(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17),(12,16,20)]

Notice the layout: when a comprehension is long, putting each qualifier on its own line with a leading comma makes it easy to scan.

let bindings

Use let inside a comprehension to name an intermediate value so you compute it once and can use it in guards and in the output. There is no in here.

HASKELL
[(x, sq) | x <- [1 .. 6], let sq = x * x, odd sq]
-- [(1,1),(3,9),(5,25)]

[(w, n) | w <- words "a quick brown fox", let n = length w, n > 1]
-- [("quick",5),("brown",5),("fox",3)]

Patterns in generators

The left side of <- can be a pattern. Elements that do not match the pattern are skipped silently, not reported as errors. This makes it easy to unwrap a list of Maybe values:

HASKELL
[a | Just a <- [Just 1, Nothing, Just 3]]
-- [1,3]

[name | (name, age) <- [("Ada", 36), ("Tim", 17)], age >= 18]
-- ["Ada"]

That skipping behaviour is specific to comprehensions (and to list do blocks). In ordinary function definitions a failed pattern is a crash, as you will see in Pattern Matching.

Nesting and infinite lists

A comprehension is an expression, so you can nest one inside another. Here the inner comprehension filters each row:

HASKELL
[[x | x <- row, even x] | row <- [[1, 2, 3], [4, 5, 6]]]
-- [[2],[4,6]]

Because lists are lazy, the source may even be infinite, as long as you ask for only a finite part of the answer:

HASKELL
take 5 [x | x <- [1 ..], x `mod` 7 == 0]
-- [7,14,21,28,35]

Only as many elements are produced as take demands. Without the take, the program would print forever.

A comprehension with an infinite generator and a guard that is never true again will hang. For example, head [x | x <- [1 ..], x < 0] searches forever. Laziness lets you skip work, not decide the undecidable.

Trying it with array methods

A comprehension is built from the same ideas as flatMap and filter. The runnable editors below use JavaScript arrays to imitate them. This is a stand-in: JavaScript arrays are strict (computed up front), so there is no infinite list here, and the notation itself exists only in Haskell.

JS Generators and guards as flatMap and filter

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

No output.

Each extra generator turns into one more flatMap, each guard into a filter, and let into a small map that remembers the helper value. That is exactly how Haskell defines the notation.

Here is the triples search, written as nested loops over arrays. It prints the same list as the Haskell version above.

JS Pythagorean triples

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

No output.

When to choose something else

Comprehensions shine for filtering and combining small lists. When a transformation is just a map or just a filter, writing map f xs or filter p xs is often shorter and clearer. When the logic has many steps, a few named helper functions read better than a comprehension with six qualifiers. Aim for something a colleague can read in a single glance.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does [x | x <- [1 .. 10], even x] evaluate to?

    The guard even x keeps only the even elements, and the output expression is x itself.
  2. 2. In [(x, y) | x <- [1, 2], y <- "ab"], which variable changes fastest?

    The later generator is like the inner loop. The result is (1,'a'), (1,'b'), (2,'a'), (2,'b').
  3. 3. What happens to elements that do not match the pattern in [a | Just a <- xs]?

    In a generator, a failed pattern simply drops that element. This is different from a function definition, where a missing case is a run-time error.
  4. 4. How do you introduce a helper name inside a comprehension?

    A let qualifier binds a name for later qualifiers and the output expression and does not use the in keyword.
  5. 5. Why is take 3 [x | x <- [1 ..], odd x] safe?

    Elements are produced on demand, so take stops the work after three results.

Summary

  • [output | qualifiers] builds a list from generators (x <- xs), guards (Bool expressions) and let bindings.
  • Several generators give every combination; the last one varies fastest, and later generators may use earlier variables.
  • Patterns on the left of <- skip non-matching elements silently.
  • Comprehensions are shorthand for map, filter and concatMap, and they work on infinite lists thanks to laziness.
  • Prefer a plain map or filter when that is all you need.

Next, look at text as a list of characters: Strings, Chars and Text.