Haskell Cartesian Product Recursively

Question

I know how to use list comprehension to do this, but how can I implement a function that will recursively compute the cartesian product given two sets?

Here's where I'm stuck (and I'm a noob)

crossProd :: [Int] -> [Int] -> [(Int,Int)]
crossProd xs ys | xs == [] || ys == [] = []
                | otherwise = (head xs, head ys) : crossProd (tail xs) (ys)

The output of this gives me

[(1,4),(1,5),(1,6)]

If the sets are [1,2,3] and [4,5,6] respectively.. How would I go about getting the rest?

Try writing a simpler case: crossProdAux :: Int -> [Int] -> [(Int,Int)] — carlosdc, Feb 15 '13 at 03:59

score 4 · Answer 1 · answered Feb 15 '13 at 04:30

4

The most basic case is this:

{-crossProdAux :: Int -> [Int] -> [(Int,Int)]-}
crossProdAux x []    = []
crossProdAux x (a:b) = (x, a):(crossProdAux x b)

{-crossProd :: [Int] -> [Int] -> [(Int,Int)]-}
crossProd [] ys   = []
crossProd (a:b) ys= (crossProdAux a ys)++(crossProd b ys)

answered Feb 15 '13 at 04:30

carlosdc

12,022
4
45
62

I'm curious, why did you comment out your type signatures? – Nicolas Wu Feb 15 '13 at 11:14
Probably because the function works for every type, not just Int. – dflemstr Feb 15 '13 at 12:29
Yeah... I didn't want to add imprecise info to the code in my answer (or, more importantly confuse the OP). – carlosdc Feb 15 '13 at 16:05

Nicolas Wu · Answer 2 · 2013-02-15T11:11:46.657

This can be done in a single function:

crossProd :: [a] -> [b] -> [(a, b)]
crossProd (x:xs) ys = map (\y -> (x, y)) ys ++ crossProd xs ys
crossProd _      _  = []

Notice that I've generalised your types so that this works for any a and b, rather than just Ints.

The key to this function is understanding that you want to pair each element in the first list with each element in the second. This solution therefore takes one element x from the first list, and pairs it with every one in ys. This is done by mapping a function that takes each value y from ys, and turns it into a pair (x, y). We add this to the front of recursing with the rest of the list xs.

In the base case, there is nothing left to pair, so the output is empty.

Haskell Cartesian Product Recursively

2 Answers2