1

I am reading through Bird and Wadler's nice book in Functional programming and trying to solve the exercises in Haskell.

The chapter on Lists has a section which says that any list comprehension can be implemented in terms of map, filter and concat and subsidiary functions which one might need for map

I am having trouble implementing the following expression in terms of these building blocks. 

[(x,y) | x<- xs, y<- ys]

How would one use map and filter for this?

I got as far as doing

concat [ map (\ a -> (a,x)) ys | x<-xs ]

I suspect we have to use currying cleverly here, but i can't seem to figure it out.

smilingbuddha
  • 14,334
  • 33
  • 112
  • 189
  • 1
    Possible duplicate of [Removing syntactic sugar: List comprehension in Haskell](http://stackoverflow.com/questions/8029046/removing-syntactic-sugar-list-comprehension-in-haskell) – Mephy Apr 25 '16 at 19:44
  • Related: http://stackoverflow.com/questions/32093912/all-combinations-of-elements-of-two-lists-in-haskell – jub0bs Apr 25 '16 at 20:03

2 Answers2

6

well for each x you need all ys so:

\x -> map (\y -> (x,y)) ys

now you only need to map this over all xs

cross xs ys = map (\x -> map (\y -> (x,y)) ys) xs

example:

> cross [1..3] "AB"
[[(1,'A'),(1,'B')],[(2,'A'),(2,'B')],[(3,'A'),(3,'B')]]
Random Dev
  • 51,810
  • 9
  • 92
  • 119
2

While I'm not sure if ApplicativeDo is allowed as part of your "building blocks", but if it is, this can easily be implemented by mapping the tuple function over the first list, and applying that list to the second.

import Control.Applicative

let xs = [1,2,3]
    ys = [4,5,6]

(,) <$> xs <*> ys

Result:

[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
Free_D
  • 577
  • 3
  • 16