Calculate n-ary Cartesian Product

Question

Given two lists, I can produce a list of all permutations the Cartesian Product of these two lists:

permute :: [a] -> [a] -> [[a]]
permute xs ys = [ [x, y] | x <- xs, y <- ys ]

Example> permute [1,2] [3,4] == [ [1,3], [1,4], [2,3], [2,4] ]

How do I extend permute so that instead of taking two lists, it takes a list (length n) of lists and returns a list of lists (length n)

permute :: [[a]] -> [[a]]

Example> permute [ [1,2], [3,4], [5,6] ]
            == [ [1,3,5], [1,3,6], [1,4,5], [1,4,6] ] --etc

I couldn't find anything relevant on Hoogle.. the only function matching the signature was transpose, which doesn't produce the desired output.

Edit: I think the 2-list version of this is essentially the Cartesian Product, but I can't wrap my head around implementing the n-ary Cartesian Product. Any pointers?

Answer 1

Here is my way of implementing it simply, using only list comprehensions.

crossProduct :: [[a]] -> [[a]]
crossProduct (axis:[]) = [ [v] | v <- axis ]
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ]

Answer 2

I found Eric Lippert's article on computing Cartesian product with LINQ quite helpful in improving my understanding of what was going on. Here's a more-or-less direct translation:

cartesianProduct :: [[a]] -> [[a]]
cartesianProduct sequences = foldr aggregator [[]] sequences
                   where aggregator sequence accumulator = 
                         [ item:accseq |item <- sequence, accseq <- accumulator ]

Or with more "Haskell-y" terse, meaningless parameter names ;)

cartesianProduct = foldr f [[]]
                    where f l a = [ x:xs | x <- l, xs <- a ]

This winds up being quite similar to sclv posted after all.