List Comprehensions

Cartesian product in an imperative language with mutable variables and loops:

function cartesianProduct(xs, ys) {
  // create array of length xs.length * ys.length
  var pairs = [];

  var i = 0;
  var j = 0;

  while (i < xs.length) {
    j = 0;
    while (j < ys.length) {
      // store new pair at pairs[i*xs.length + j]
      pairs.push([xs[i], ys[j]]);
      j++;
    }
    i++;
  }

  return pairs;
}

% node loop.js
[ [ 1, 'a' ], [ 1, 'b' ], [ 1, 'c' ],
  [ 2, 'a' ], [ 2, 'b' ], [ 2, 'c' ],
  [ 3, 'a' ], [ 3, 'b' ], [ 3, 'c' ],
  [ 4, 'a' ], [ 4, 'b' ], [ 4, 'c' ],
  [ 5, 'a' ], [ 5, 'b' ], [ 5, 'c' ] ]

"Looping" Over Lists Via Recursion

cartesianProduct :: [a] -> [b] -> [(a, b)]
cartesianProduct xs ys =
  concat $ map (\x -> map (\y -> (x, y)) ys) xs

> cartesianProduct [1..5] "abc"

Common pattern:

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f xs = concat $ map f xs
concatMap f    = concat . map f

(Note: we'll soon see how concatMap can be defined to satisfy a more general type.)

cartesianProduct3 :: [a] -> [b] -> [c] -> [(a, b, c)]
cartesianProduct3 xs ys zs =
  concatMap (\x -> concatMap (\y -> map (\z -> (x, y, z)) zs) ys) xs

> cartesianProduct [1..5] "abc" [True, False]

Recall the following operator for reverse infix application (a.k.a. "forward pipelining"):

(|>) :: a -> (a -> b) -> b
x |> f = f x

We can use this to define cartesianProduct3 more clearly:

cartesianProduct3 xs ys zs =
  xs |> concatMap (\x ->
    ys |> concatMap (\y ->
      zs |> map (\z ->
        (x, y, z)
      )
    )
  )

Or:

cartesianProduct3 xs ys zs =
  xs |> concatMap (\x ->
  ys |> concatMap (\y ->
  zs |> map (\z ->
    (x, y, z)
  )))

One last improvement: let's turn the innermost call to map into concatMap, to continue the pattern:

cartesianProduct3 xs ys zs =
  xs |> concatMap (\x ->
  ys |> concatMap (\y ->
  zs |> concatMap (\z ->
    [(x, y, z)]
  )))

EXERCISE: Can a similar style as above be achieved without using the (|>) operator?

As a variation on cartesianProduct, let's return only those pairs where the first component is less than the second:

lessThanPairs :: Ord a => [a] -> [a] -> [(a, a)]
lessThanPairs xs ys =
  cartesianProduct xs ys
    |> filter (uncurry (<))

> lessThanPairs [1..5] [1..5]
[(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)]

To avoid the post-processing filtering pass:

lessThanPairs xs ys =
  xs |> concatMap (\x ->
  ys |> concatMap (\y ->
    if x < y
      then [(x,y)]
      else []
  ))

Cleaning up with a helper definition:

lessThanPairs xs ys =
  concatMap (\x -> concatMap (maybeAddPair x) ys) xs
  where
    maybeAddPair x y | x < y     = [(x,y)]
                     | otherwise = []

Not bad, but Haskell provides some syntactic sugar for "looping" over lists.

List Comprehensions

Resembling the set comprehensions found in mathematical notation, a list comprehension is an expression of the form

[ expression | things ]

where each thing takes one of the following forms

thing ::=
  | let x = e    let-binding
  | x <- xs      "generator"
  | e            `Bool`ean predicate (for filtering)

and where things are separated by commas.

For example:

squares :: Num a => [a] -> [a]
squares xs =
  [ x^2 | x <- xs ]

cartesianProduct :: [a] -> [b] -> [(a, b)]
cartesianProduct xs ys =
  [ (x, y) | x <- xs, y <- ys ]

lessThanPairs :: Ord a => [a] -> [a] -> [(a, a)]
lessThanPairs xs ys =
  [ (x, y) | x <- xs, y <- ys, x < y ]

smallPairs :: (Ord a, Num a) => [a] -> [a] -> [(a, a)]
smallPairs xs ys =
  [ (x, y) | x <- xs, y <- ys, let sum = x + y, sum <= 5 ]

The list comprehension [ expression | things ] gets desugared as follows, where the desugaring [[ things ]] refers to the expression when the entire list of things has been desugared:

[[ let x = e, things ]]  ===  let x = e in [[ things ]]
[[    x <- e, things ]]  ===  flip concatMap e (\x -> [[ things ]])
[[         e, things ]]  ===  if not e then [] else [[ things ]]
[[                   ]]  ===  [expression]

Source Files

• ListComprehensions.hs
• loop.js