## Cartesian Product

### September 6, 2013

Today’s exercise is another interview question from our unending supply of interview questions. Beware that it’s a tough one:

Write a function that takes a variable number of lists and returns the cartesian product (sometimes called the cross product) of the items in the lists. For instance, the cartesian product of the lists (1 2 3), (4) and (5 6) is the list of lists ((1 4 5) (1 4 6) (2 4 5) (2 4 6) (3 4 5) (3 4 6)). You should provide both recursive and iterative versions of your function.

Your task is to write the cartesian product function as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

A recursive Haskell version:

cart [] = [[]]

cart (xs:xss) = [ x:ys | x <- xs, ys <- cart xss ]

Simple-minded recursion:

(define (X . sets)

(if (null? sets) '(())

(let ((tails (apply X (cdr sets))))

(apply append

(map (lambda (h)

(map (lambda (t) (cons h t)) tails))

(car sets))))))

`;(X '(1 2 3) '(4) '(5 6))`

;==> ((1 4 5) (1 4 6) (2 4 5) (2 4 6) (3 4 5) (3 4 6))

Differently iterative:

(define (for-X proc . sets)

(if (null? sets) (proc '())

(for-each

(lambda (head)

(apply for-X (lambda (tail)

(proc (cons head tail)))

(cdr sets)))

(car sets))))

`;(for-X write '(1 2 3) '(4) '(5 6)) ==> unspecified`

;displays: (1 4 5)(1 4 6)(2 4 5)(2 4 6)(3 4 5)(3 4 6)

A Python version. In Python this functionality is already in library itertools (product).

Another recursive implementation in Common Lisp:

And, for fun, here is one with macros, generating a separate loop for every level:

Here is an iterative and recursive C# solution:

Haskell doesn’t really have functions with variable numbers of arguments, and faking such is more for programmers of Okasaki’s caliber than mine, so I’ll just have it take a list of lists. I started out with a recursive solution, then realized I could make it a little prettier:

Then I looked on the Internet for advice. Oddly enough, it turns out that Haskell has Cartesian products in the Prelude, but not in an obvious way.

does the trick. It took me a while to figure out how it works, so I figured I’d type up my reasoning below:

sequence is actually a rather more general. Here’s how it’s defined at http://hackage.haskell.org/package/base-4.6.0.1/docs/src/Control-Monad.html#sequence

The funky return [] can immediately be rewritten based on the instance declaration for lists in http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC-Base.html#Monad partially copied below:

In particular, note that return [] is actually the same as [[]]. Also, for lists, we can translate the do notation directly to list comprehension notation, so the above definition for sequence, specialized to lists, is written much more transparently thus:

Now it’s much clearer what is going on: this is just translating the Cartesian product of [l1,l2,…,ln] into l1*(l2*(l3*…)).

Now how is that do notation or list comprehension treated under the hood? Well, it’s translated to

Now what does that funky >>= do? Well, m >>= k is foldr ((++).k) [] m, which is not immediately helpful. But letting m=[m1,m2,…,mn] and expanding the foldr simplifies things a drop:

It’s still a tad weird, though. What the heck is (++).k? It’s a function, obviously, that takes a value, applies k to it, and then applies (++) to the result. Writing this out, it’s

or, equivalently,

That is, p `(++).k` q = k(p) ++ q.

Substituting this in, m >>= k becomes much simpler:

so we’re just applying k to each of the elements of m and concatenating the results!

So

just means that for each element x of m, for each element xs of m’ we form the list [x:xs], concatenate these together to form [x:xs1++x:xs2++…], and concatenate those together to form [x1:xs1++x1:xs2++…++x2:xs1++x2:xs2++…], which is the Cartesian product.

Which is the Cartesian product of x with xs, I should say. Now that I understand what the helper function “k” in sequence does, the operation of sequence becomes clear.