Cartesian product of 2 lists in Haskell

There is a very elegant way to do this with Applicative Functors:

import Control.Applicative

(,) <$> [1,2,3] <*> [4,5,6]
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

The basic idea is to apply a function on "wrapped" arguments, e.g.

(+) <$> (Just 4) <*> (Just 10)
-- Just 14

In case of lists, the function will be applied to all combinations, so all you have to do is to "tuple" them with (,).

See http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors or (more theoretical) http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf for details.

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]]

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]