[Haskell-cafe] Converting list comprehensions to combinatory style

[Daniel Fischer]

Am Samstag, 7. März 2009 23:06 schrieb R J:
> Can anyone help with this problem from Bird:
>
> a. Convert the following list comprehensions to combinatory style:
>
>    i.   [(x, y) | x <- [1..n], odd x, y <- [1..n]]
>    ii.  [(x, y) | x <- [1..n], y <- [1..n], odd x]
>
> b. Are they equal?
>
> c. Compare the costs of evaluating the two expressions.
>
> I gather that by combinatory style, he means the use of concat, map, and
> filter.  While Bird provides the following conversion rules, he doesn't
> prove them, justify them, or even provide an example using them:
>
>    R1.  [ f x | x <- xs      ]  =  map f xs
>    R2.  [   x | x <- xs, p x ]  =  filter p xs
>    R3.  [ e   | Q, P         ]  =  concat [[e | P] | Q]
>    R4.  [ e   | x <- [d | P] ]  =  [e [x := d] | Q, P]
>
> Thanks.

You can take R1-R4 as definition of the list-comprehension syntax.

Then you can rewrite i. step by step:

[(x,y) | x <- [1 .. n], odd x, y <- [1 .. n]]
~> concat [[(x,y) | y <- [1 .. n]] | x <- [1 .. n], odd x]]
~> concat [map (\y -> (x,y)) [1 .. n] | x <- [1 .. n], odd x]
~> concat (map (\x -> map (\y -> (x,y)) [1 .. n]) (filter odd [1 .. n]))

(okay, I cheated, the last step is actually a sequence of steps, transforming
[f x | x <- xs, p x] into map f (filter p xs)).