Nested Iteration
We can also generate a list that contains one entry for every pair of values taken from a pair of lists:
>>> [(x, y) | x <- [1..3], y <- [10..12]]
[(1,10),(1,11),(1,12),(2,10),(2,11),(2,12),(3,10),(3,11),(3,12)]
As this example shows, we can think about this as two nested loops where the
outer loop iterates over the x values and the inner loop iterates over the y
values. So we first have all the pairs with the first component equal to 1, and
the second components of these pairs iterate from 10 to 12, then we have all the
pairs with the first component equal to 2, and the second components of these
pairs iterate from 10 to 12 again, and so on. But we don't have to combine x
and y into a pair. We can once again combine them using whatever function we
want:
>>> import Data.Char
>>> [a * ord b | a <- [1..3], b <- "Hello"]
[72,101,108,108,111,144,202,216,216,222,216,303,324,324,333]
And we can also nest more than two "loops":
>>> [a + b + c | a <- [0,100], b <- [0,10], c <- [0,1]]
[0,1,10,11,100,101,110,111]
In the examples so far, the "inner loops" were completely independent of the "outer loops". When implementing nested loops in imperative languages, the range of values that the inner loops iterate over can depend on the loop variables of the surrounding loops. We can do the same with list comprehensions. For example, here is how we enumerate all pairs \((x,y)\) with \(1 \le x < y \le 5\):
>>> [(x,y) | x <- [1..4], y <- [x+1..5]]
[(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)]
You can read this as: For every x taken from the list [1..4], take y from
the list [x+1..5] and add the pair (x,y) to the list produced by this list
comprehension.
Exercise
Remember good old concat. It takes a list of lists and concatenates them:
>>> concat [[1,2],[],[3,4],[5]]
[1,2,3,4,5]
The standard implementation is
concat = foldr (++) []
Use a list comprehension to implement concat instead.
Solution
concat xss = [x | xs <- xss, x <- xs]
This says: Build the list containing every x in xs, for every xs
in xss. That's exactly what the concatenation of a list of lists is.