[Haskell-cafe] Converting list comprehensions to combinatory style

R J rj248842 at hotmail.com
Sat Mar 7 17:06:37 EST 2009

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]


Windows Live™ Groups: Create an online spot for your favorite groups to meet.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090307/f11ecd3b/attachment.htm

More information about the Haskell-Cafe mailing list