Having trouble understanding list comprehensions

Question

I've just started learning haskell(literally, tonight!) and I'm having a little trouble understanding the logic of list comprehensions, more specifically the <- operator. A little example on Learn You Some Haskell Finds all tuples that have a length less than 10:

ghci> let triangles = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10] ]

my initial understanding was that these would all increment together, but after seeing the output I really dont understanding the incrementing method for these lists. Another example that seems to get me is:

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

I would really appreciate a little explanation on these, thanks for your patience with my lack of haskell intelligence.

Answer 1

Read [ as "list of", | as "for", <- as "in", , as "and".

The enumerations are done in nested fashion. [ (a,b,c) | c <- [1..10], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2] is really

for c from 1 to 10 step 1:
   for b from 1 to c step 1:
      for a from 1 to b step 1:
          if (a^2 + b^2 == c^2):
             emit (a,b,c)

In Haskell though, the above is achieved by the following translation

[1..10] >>= (\c->               -- (a function of 'c', producing ...
  [1..c]  >>= (\b->               -- (a function of 'b', producing ...
    [1..b]  >>= (\a->               -- (a function of 'a', producing ...
      if a^2+b^2==c^2 then [(a,b,c)] else []
      -- or: [(a,b,c) | a^2+b^2==c^2]
      )))

so you really can see the nested structure here. (>>=) is nothing mysterious too. Read >>= as "fed into" or "pushed through", although its official name is "bind". It is defined (for lists) as

(xs >>= f) = concatMap f xs = concat (map f xs)

f here is called (by map) upon each element of xs, in order. It must produce lists so that they could be combined with concat. Since empty lists [] are eliminated on concat (e.g. concat [[1], [], [3]] == [1,3]) all the elements that do not pass the test are eliminated from the final output.

---

For the full translation see section 3.11, List Comprehensions, of the Haskell 98 Report. In general a list comprehension may contain a pattern, not just a variable name. The comprehension

[e | pat <- ls, ...]  

is translated as

ls >>= (\x -> case x of pat -> [e | ...] ;
                        _   -> [] )

where pat is some pattern, and x is a fresh variable. When there's a pattern mismatch, an empty list is produced (instead of a run-time error), and that element x of ls is skipped over. This is useful for additional pattern-based filtering, like e.g. [x | Just x <- ls, even x] where all the Nothings in ls are quietly ignored.

Answer 2

[ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10] ] means, for all combinations of (a,b,c) where a is in [1..10], b is in [1..10], c is in [1..10]

If you want the (1,1,1) (2,2,2) kinds, you should use zip: zip [1..10] [1..10] or for 3 lists, zip3 [1..10] [1..10] [1..10]

Answer 3

I think of list comprehension syntax as Haskell's attempt to get Set-builder notation in the language. We use '[' rather than '{' and '<-' rather than '∈'. List comprehension syntax can even be generalized to arbitrary monads.