Skip to content

List Comprehensions Revisited

This section is entirely optional reading.

When discussing list comprehensions, we discussed how the expressions [1..10], [1..], [1,3..10], and [1,3..] are translated into function calls enumFromTo 1 10, enumFrom 1, enumFromThenTo 1 3 10, and enumFromThen 1 3. We also discussed additional list comprehensions that allow us to mimic mapping, filtering, zipping lists together, and combining lists in a manner akin to nested loops.

I mentioned that parallel list comprehensions, used to mimic zipping of lists, are a language extension in GHC. They are not part of standard Haskell. The reason is historical. In very early versions of Haskell, comprehensions were available not only for lists but in fact for every monad. It turns out that mapping, filtering, and nested loops can all be desugared using do-notation, that is, they are expressible for any monad (only they may behave very differently, depending on the decoration provided by the monad).1 The same is not true for parallel list comprehensions. Thus, they were not supported in early versions of Haskell and were added only later, after restricting comprehensions only to lists.2

So let's ignore parallel list comprehensions here and figure out how all the other constructs can be translated into computations that use the list monad.

Let's start with a complex example, one we used before:

GHCi
>>> products = [x * y | x <- [1..10], even x, y <- [x..10], odd (x + y)]
>>> products
[6,10,14,18,20,28,36,42,54,72]

This says that we want to take each element x from the list [1..10], discard the ones that are not even, for each x that is not discarded, take each element y from the list [x..10], discard those that do not satisfy odd (x + y), and for those that are not discarded, add the product x * y to the result. Note how this description sounds rather imperative: Take each element x from the list [1..10], discard the ones that are not even, and so on. Since monads allows us to pretend we program imperatively, the translation into using the list monad is a one-to-one mapping of this description:

products = do
    x <- [1..10]
    guard $ even x
    y <- [x..10]
    guard $ odd (x + y)
    return $ x * y
GHCi
>>> :{
  | products = do
  |     x <- [1..10]
  |     guard $ even x
  |     y <- [x..10]
  |     guard $ odd (x + y)
  |     return $ x * y
  | :}
>>> products
[6,10,14,18,20,28,36,42,54,72]

It surely produces the same result. How does this work? Remember the logic of the (>>=) operator for the list monad. In the expression xs >>= f, we apply f to every element in the list xs and concatenate the lists produced by these applications: xs >>= f = concatMap f xs. Let's desugar the do-block:

products = [1..10] >>= \x -> guard (even x)
                   >>= \_ -> [x..10]
                   >>= \y -> guard (odd (x + y))
                   >>= \_ -> return (x * y)

Now let's put this together from back to front. The function \_ -> return (x * y) maps its argument (which it ignores) to the list [x * y], because return z = [z]. The function \y -> guard (odd (x + y)) >>= \_ -> return (x * y) applies this function to every element in the list produced by guard (odd (x + y)). This list is [()] if odd (x + y) is true, and [] otherwise. Thus, the function \y -> guard (odd (x + y)) >>= \_ -> return (x * y) returns the list [x * y] if x + y is odd, and [] otherwise. The function \_ -> [x..10] >>= \y -> guard (odd (x + y)) >>= \_ -> return (x * y) applies this function to each value y in the list [x..10] and concatenates the results. Thus, it produces the list of all values x * y where y belongs to [x..10] and x + y is odd. The function \x -> guard (even x) >>= \_ -> [x..10] >>= \y -> guard (odd (x + y)) >>= \_ -> return (x * y) evaluates this expression for each element in the list guard (even x), that is, it produces the empty list if x is odd. If x is even, then it produces the list of products x * y where y is taken from the list [x..10] and x + y is odd. The whole expression [1..10] >>= \x -> ... then evaluates this expression for every value x in the list [1..10]. So, we get the list of all products x * y where x is taken from the list [1..10], x is even, y is taken from the list [x..10], and x + y is odd. That says exactly the same thing as our list comprehension.

In general, a list comprehension is of the form

[expr | clause1, clause2, ...]

where each clause is either an assignment pat <- expr, such as x <- [1..10], or some condition, such as even x. This translates into the do-block

do statement1
   statement2
   ...
   return expr

where the \(i\)th statement is obtained from the \(i\)th clause:

  • If the \(i\)th clause is an assignment pat <- expr, then the \(i\)th statement is the same assignment.

  • If the \(i\)th clause is a condition cond, then the \(i\)th statement is the expression guard cond.

In the list comprehension

[x * y | x <- [1..10], even x, y <- [x..10], odd (x + y)]

we have four clauses

  • x <- [1..10]
  • even x
  • y <- [x..10]
  • odd (x + y)

and the expression is x * y. According to the desugaring rules just discussed, this translates into

do x <- [1..10]
   guard (even x)
   y <- [x..10]
   guard (odd (x + y))
   return (x * y)

exactly the do-block we came up with above.

  1. Well, it actually seems that to express filtering, we need a monad that can handle failure, that is, a monad that is an instance of the MonadFail subclass of the Monad class. I'm not sure how filtering was implemented for arbitrary monads in early versions of Haskell. ↩

  2. The history of comprehensions has another twist to it. Initially, comprehensions were supported for all monads. Then this support was dropped, and we had only list comprehensions. Nowadays, GHC has several language extensions that make comprehensions more general.

    First, there's the OverloadedLists extension, which generalizes list comprehensions to fairly arbitrary sequence types. Specifically, with this extension turned on, any type that is an instance of the IsList type class supports comprehensions. This includes lists, the Array type, the Vector type in the vector package, and a few others.

    Next, there's the MonadComprehensions extension. This brings back the original behaviour that comprehensions are supported for all monads.

    Finally, there is the TransformListComp extension, which introduces SQL-like extensions to the list comprehension syntax.

    If you're adventurous, you can read about these extensions here. ↩