Cartesian product of 2 lists in Haskell

I wish to produce the Cartesian product of 2 lists in Haskell, but I cannot work out how to do it. The cartesian product gives all combinations of the list elements:

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

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys ==> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

This is not an actual homework question and is not related to any such question, but the way in which this problem is solved may help with one I am stuck on.

This is very easy with list comprehensions. To get the cartesian product of the lists xs and ys, we just need to take the tuple (x,y) for each element x in xs and each element y in ys.

This gives us the following list comprehension:

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

As other answers have noted, using a list comprehension is the most natural way to do this in Haskell.

If you're learning Haskell and want to work on developing intuitions about type classes like Monad, however, it's a fun exercise to figure out why this slightly shorter definition is equivalent:

import Control.Monad (liftM2)

cartProd :: [a] -> [b] -> [(a, b)]
cartProd = liftM2 (,)

You probably wouldn't ever want to write this in real code, but the basic idea is something you'll see in Haskell all the time: we're using liftM2 to lift the non-monadic function (,) into a monad—in this case specifically the list monad.

If this doesn't make any sense or isn't useful, forget it—it's just another way to look at the problem.

If your input lists are of the same type, you can get the cartesian product of an arbitrary number of lists using sequence (using the List monad). This will get you a list of lists instead of a list of tuples:

> sequence [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]