How are dependent ranges computed in a list comprehension?

Question

I'm currently making my way through Learn You a Haskell for Great Good!, and I'm confused on the penultimate example in Chapter 2.

As a way of generating triples representing all right triangles with all sides that are whole numbers less than or equal to 10, he gives this definition:

rightTriangles = [ (a,b,c) | c <- [1..10], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2] 

What I'm specifically confused about is the fact that b is bound to a list that ranges from 1 to c, and similarly with a. If my understanding is correct, c will be evaluated to all values in the list it is bound to, but I still don't see which value is being used for c in the range (e.g. all values of c, only the first c, etc.)

If it's not too much, a step by step explanation of how this evaluates would be great. :)

Thanks in advance!

Answer 1

Let's consider two simpler list comprehensions:

ex1 = [(a,b) | a <- [1..3], b <- [1..3]]

ex2 = [(a,b) | a <- [1..3], b <- [1..a]]

They're almost the same, but in the second case, b ranges from 1 to a, not 1 to 3. Let's consider what they're equal to; I've formatted their values in such a way as to make a point.

ex1 = [ (1,1), (1,2), (1,3)
      , (2,1), (2,2), (2,3)
      , (3,1), (3,2), (3,3) ]

ex2 = [ (1,1),
      , (2,1), (2,2),
      , (3,1), (3,2), (3,3) ]

In the first example, the list comprehension draws every possible combination of elements from [1..3] and [1..3]. But since we're talking about lists, not sets, the order it does that in is important. Thus, in more detail, what ex1 really means is this:

• Let a be equal to every possible value from its list.
  • For each value of a, let b be every possible value from its list.
    • (a,b) is an element of the output list

Or, rephrased: "for every possible value of a, compute (a,b) for every possible value of b." If you look at the order of the results, this is what happens:

1. For the first three elements, a is equal to 1, and we see it paired with every value of b.
2. For the next three elements, a is equal to 2, and we see every value of b.
3. And finally, for the last three elements, a is equal to 3 and we see every value of b.

In the second case, much the same thing happens. But because a is picked first, b can depend on it. Thus:

1. First, a is equal to 1, and we see it paired with every possible value of b. Since b <- [1..a], that means b <- [1..1], and so there's only one option.
2. After one element, then, a is equal to 2, and we see that paired with every possible value of b. Now that means b <- [1..2], and so we get two results.
3. Finally, a is equal to 3, and so we're picking b <- [1..3]; this gives us the full set of three results.

In other words, because the list comprehensions rely on an ordering, you can take advantage of that. One way to see that is to imagine translating these list comprehensions into nested list comprehensions:

ex1 = concat [ [(a,b) | b <- [1..3]] | a <- [1..3] ]

ex2 = concat [ [(a,b) | b <- [1..a]] | a <- [1..3] ]

To get the right behavior, a <- [1..3] must go on the outside; this ensures that the bs change faster than the as. And it hopefully makes it clear how b can depend on a. Another translation (basically the one used in the Haskell 2010 Report) would be:

ex1 = concatMap (\a -> [(a,b) | b <- [1..3]]) [1..3]
    = concatMap (\a -> concatMap (\b -> [(a,b)]) [1..3]) [1..3]

ex2 = concatMap (\a -> [(a,b) | b <- [1..a]]) [1..3]
    = concatMap (\a -> concatMap (\b -> [(a,b)]) [1..a]) [1..3]

Again, this makes the nesting very explicit, even if it's hard to follow. Something to keep in mind is that if the selection of a is to happen first, it must be on the outside of the translated expression, even though it's on the inside of the list comprehension. The full, formal translation of rightTriangles would then be

rightTriangles =
  concatMap (\c ->
    concatMap (\b ->
      concatMap (\a ->
        if a^2 + b^2 == c^2
          then [(a,b,c)]
          else []
      ) [1..b]
    ) [1..c]
  ) [1..10]

---

As a side note, another way to write rightTriangles is as follows:

import Control.Monad (guard)

rightTriangles = do c <- [1..10]
                    b <- [1..c]
                    a <- [1..b]
                    guard $ a^2 + b^2 == c^2
                    return (a,b,c)

You probably haven't used do notation yet, and certainly not for anything but IO, so I'm not saying you should necessarily understand this. But you can read the x <- list lines as saying "for each x in list", and so read this as a nested loop:

rightTriangles = do
  c <- [1..10]             -- For each `c` from `1` to `10`, ...
  b <- [1..c]              -- For each `b` from `1` to `c`, ...
  a <- [1..b]              -- For each `a` from `1` to `b`, ...
  guard $ a^2 + b^2 == c^2 -- If `a^2 + b^2 /= c^2`, then `continue` (as in C);
  return (a,b,c)           -- `(a,b,c)` is the next element of the output list.

Note that the continue only skips to the next iteration of the innermost loop in this interpretation. You could also write it as

rightTriangles = do c <- [1..10]
                    b <- [1..c]
                    a <- [1..b]
                    if a^2 + b^2 == c^2
                      then return (a,b,c)
                      else [] -- or `mzero`

Where the last lines say "if a^2 + b^2 == c^2, add (a,b,c) to the output list; otherwise, add nothing." I only mention this because I thought seeing it written this way might help make the "nested loop"-type structure that's going on clear, not because you should fully understand do-notation while reading Chapter 2 of Learn You A Haskell :-)

Answer 2

Seeing you have experience with imperative programming, a short answer would be: similar to this for nesting (pseudo code):

for(c = 1; c <= 10; c++) {
    for(b = 1; b <= c; b++) {
        for(a = 1; a <= b; a++) {
            if(a ^ 2 + b ^ 2 == c ^ 2) {
                list.append((a, b, c));
            }
        }
    }
}