# 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 `filter`ing 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 `thing`s 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]``````