[Haskell-cafe] Converting list comprehensions to combinatory style
daniel.is.fischer at web.de
Sat Mar 7 17:36:29 EST 2009
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]
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)).
More information about the Haskell-Cafe