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]
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 =
filter (uncurry (<))
(concatMap (\x -> map (\y -> (x, y)) ys) xs)
> 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 =
concatMap (\x -> concatMap (\y -> if x < y
then [(x,y)]
else []
) ys
) xs
Cleaning up with a helper definition:
lessThanPairs xs ys =
concatMap (\x -> concatMap (addPair x) ys) xs
where
addPair 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]