Note A2: List Comprehensions
Mathematicians have a concise notation for describing a set, which typically involves describing an initial set, a predicate, and a form for elements of that set, e.g., $\{ x^2 \mid \hbox{$x \in \omega$ and $x$ is even}\}$, the squares of all even natural numbers. These are called set comprehensions. Haskell provides a similar notation for lists:
> [x^2 | x <- [1..10], even x]
[4,16,36,64,100]
It is possible in list comprehensions to have multiple generators, let bindings, and to interleave generations, tests, and bindings. As a simple example, let's generate all of the pythagorean triples that where the hypotenuse is less than a given number:
pythagoreanTriples n =
[ (a,b,c)
| a <- [1..n]
, b <- [a+1..n]
, c <- [b+1..n]
, a^2 + b^2 == c^2
]
> pythagoreanTriples 20
[(3,4,5),(5,12,13),(6,8,10),(8,15,17),(9,12,15),(12,16,20)]
Note that the results are sorted by a, because the generation runs like this, for each a from 1 to n, generate b from a+1 to n, and for each such a and b, generate c from b+1 to n...
Also note our use of tuples. Tuples look like lists, but they're very different. We'll talk about them more next lecture, but for now, they're a convenient way to package up a few values.
But notice that this list contains a few non-primitive triples, e.g., (6,8,10), (9,12,15), and (12,16,20), which are all multiples of (3,4,5). Suppose we wanted to restrict ourselves to primitive triples, i.e., tuples that are relatively prime to one onother. How might we do that? A simple approach would be to filter out those triples where a and b have a non-trivial common divisor, i.e.,
primitiveTriples n =
[ (a,b,c)
| a <- [1..n]
, b <- [a+1..n]
, gcd a b == 1
, c <- [b+1..n]
, a^2 + b^2 == c^2
]
It is more efficient to do the gcd test before the generation of c, because otherwise we'd have to repeat the same test (on a and b alone) for each c; but it should be noted too that our basic computational plan emphases clarity over efficiency, and there are much more efficient ways to generate lists of pythagorean triples.