List comprehensions

30 July 2023

List comprehensions are an elegant syntactic construct for creating and transforming lists. They are succinct and powerful, and available in several languages. In Haskell particularly, the syntax has the same form as that of the mathematical set-builder notation, which looks like

\{\underbrace{x^2}_{\text{output}} \mid \underbrace{x}_{\text{variable}} \in \underbrace{\mathbb{N}}_{\text{input}}, \underbrace{x<10}_{\text{predicate}}\}

The Haskell list comprehension1 for this set is

[ x^2 | x <- [0..], x < 10 ]

Here [0..] corresponds to the natural numbers.2 The expression x <- [0..] is called a generator, and the predicate is called a guard.

List comprehensions can have multiple generators, separated by commas.

[ (x, y) | x <- [0,1], y <- ['a', 'b']] 

Later (rightmost) generators iterate “faster” than earlier ones (those on the left); in the above example, the entirety of y is iterated for each element of x. The behavior is the same as nested loops in imperative languages. Because of this, the order of the generators impacts the result:

[ (x, y) | y <- ['a', 'b'], x <- [0,1] ] 

Later generators can depend on variables introduced by earlier generators.

[ (x, y) | x <- [0..2], y <- [x..2]] 

Using this feature, we can, for example, define the concat function that concatenates lists:

concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]

concat [[1,2,3], [4,5], [6]]

List comprehensions can also have multiple independent branches of qualifier (input) lists, each separated by the | symbol. These are called parallel list comprehensions. For example, the following zips together two lists:

[ (x, y) | x <- [0..2] | y <- ['a'..'c'] ] 

As a final, more interesting example, let’s implement the popular FizzBuzz kata / interview question. Let’s use a list comprehension to solve this using what Seemann calls the resonance approach.3 Basically, we define two periodic streams (infinite sequences), one for fizz (with a period of 3) and one for buzz (with a period of 5).4 We also define a sequence of all integers [1..]. Once we have these three streams defined, we just combined them index-wise with a parallel list comprehension!

We’ll use a List of type Maybe String for fizz and buzz to easily combine the list items with the mappend operator (<>). Since both Maybe and String ([Char]) are monoids, they both support mappend. We’ll use fromMaybe5 to combine the number stream with the combined fizz and buzz streams. The type of fromMaybe is fromMaybe :: a -> Maybe a -> a. It takes a first argument of type a, which will be returned if the value of the second argument Maybe a is Nothing. Otherwise it returns the a value carried by the Just value of the Maybe type.

fizz = cycle [Nothing, Nothing, Just "Fizz"] 
buzz = cycle [Nothing, Nothing, Nothing, Nothing, Just "Buzz"]
fizzbuzz = [fromMaybe (show n) (f <> b) | n <- [1..] | f <- fizz | b <- buzz ]
take 15 fizzbuzz

That’s it!

List comprehensions are a succinct and powerful way to manipulate lists. I hope this brief summary / intro inspires you to find good use for them.

  1. Of course, a list is an ordered collection of potentially repeatable elements, not a set, but the syntax is the same.↩︎

  2. Because Haskell is a lazy language, infinite lists like this one can be safely declared.↩︎

  3. I really like this approach because of its affinity to music / signal processing.↩︎

  4. The periods could be anything, but we set these to 3 and 5 because these are the typical values used.↩︎

  5. You need to import Data.Maybe.↩︎

Spread the Word