List Comprehensions

Cartesian product in an imperative language, using 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;
}

var xs = [1, 2, 3, 4, 5];
var ys = ['a', 'b', 'c'];
console.log(cartesianProduct(xs, ys));

% node cartesian-product.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

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

> cartesianProduct3 [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)]
  )))

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

A list comprehension is an expression form that resembles a set comprehension from mathematical notation. 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 ]

See the syntax reference for the general structure [ returnExp | stmt_1 , … , stmt_n ] , and how it gets desugared to ordinary “looping” over lists.

Source Files

• ListComprehensions.hs
• cartesian-product.js