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)). _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
