# [Haskell-cafe] Calculating with list comprehension

Dan Weston westondan at imageworks.com
Thu Mar 5 22:14:38 EST 2009

```Keep in mind this is a *lexical* rewrite. In the generator rule x and e
are not independent: x is a pattern (which introduces a bind variable)
and e is an expression (with free variables, one of which may be bound by x)

After one application of the generator rule, we get (using a lambda
expression instead of introducing a fresh function name f):

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

After another:

concatMap (\a -> concatMap (\b -> [(a,b)]) [1..2]) [1..3]

Note that the "a <-" and "b <-" map into \a -> and \b -> and bind the
free variables a and b in the expression (a,b).

Dan

R J wrote:
> I can calculate non-nested list comprehensions without a problem, but am
> unable to calculate nested comprehensions involving, for example, the
> generation of a list of pairs where the first and separate elements are
> drawn from two separate lists, as in:
>
>    [(a, b) | a <- [1..3], b <- [1..2]]
>
> How does one calculate the expansion of this list?  The two rules for
> expanding list comprehensions are:
>
> 1.  Generator rule:  [e | x <- xs, Q]  =  concat (map f xs)
>                                           where
>                                               f x = [e | Q]
>
> 2.  Guard rule:      [e | p, Q]        =  if p then [e | Q] else []
>
>
> There is a third rule that I've seen on the Internet, not in an
> authoritative text:
>
>    [e | Q1 , Q2]     =  concat [ [e | Q 2] | Q1 ]
>
> I don't understand what this third rule means, or whether it's relevant.
>
> Concat and map are defined as:
>
> concat           :: [[a]] -> [a]
> concat []        =  []
> concat (xs:xss)  =  xs ++ concat xss
>
> map              :: (a -> b) -> [a] -> [b]
> map f []         =  []
> map f (x:xs)     =  f x : (map f xs)
>
> Any help is appreciated.
>
>
>
> ------------------------------------------------------------------------
> Windows Live™: Keep your life in sync. Check it out.
> <http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1b_explore_032009>
>

```