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 comprehension^{1} for this set is

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

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 <- [0,1], y <- ['a', 'b']]
[ (x, y) ==
0,'a'),(0,'b'),(1,'a'),(1,'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:

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

Later generators can depend on variables introduced by earlier generators.

```
| x <- [0..2], y <- [x..2]]
[ (x, y) ==
0,0),(0,1),(0,2),(1,1),(1,2),(2,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]]
=
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 <- [0..2] | y <- ['a'..'c'] ]
[ (x, y) ==
0,'a'),(1,'b'),(2,'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
`fromMaybe`

^{5} 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.

```
= cycle [Nothing, Nothing, Just "Fizz"]
fizz = cycle [Nothing, Nothing, Nothing, Nothing, Just "Buzz"]
buzz = [fromMaybe (show n) (f <> b) | n <- [1..] | f <- fizz | b <- buzz ]
fizzbuzz take 15 fizzbuzz
==
"1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","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.

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

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

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

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

You need to

`import Data.Maybe`

.↩︎