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)).