views:

215

answers:

4

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?

+8  A: 
Prelude> sequence [[1,2],[3,4],[5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
jleedev
While sequence does solve the problem, I was really interested in how this would work. The [implementation](http://haskell.org/ghc/docs/6.12.1/html/libraries/base-4.2.0.0/src/Control-Monad.html#sequence) uses monads; is there a way to calculate the product without using monads? (eg in a language that doesn't include monads)
BleuM937
@BleuM937: For the list monad, `sequence` means "for each element in the first list, prepend it to each list obtained by sequencing the remaining lists". It's basically the most obvious way to write a Cartesian product using a right fold.
camccann
+3  A: 

As a supplement to jleedev's answer (couldn't format this in the comments):

A quick unchecked substitution of list functions for monadic ones:

sequence ms = foldr k (return []) ms
   where
    k m m' = do { x <- m; xs <- m'; return (x:xs) }

....

    k m m' = m >>= \x -> m' >>= \xs -> [x:xs]
    k m m' = flip concatMap m $ \x -> flip concatMap m' $ \xs -> [x:xs]
    k m m' = concatMap (\x -> concatMap (\xs -> [x:xs]) m') m

....

sequence ms = foldr k ([[]]) ms
   where
     k m m' = concatMap (\x -> concatMap (\xs -> [x:xs]) m') m
sclv
That can be slightly simplified further by eliminating a superfluous concatenation in `k m m' = concatMap (\x -> map (x:) m') m`. Could also write it as a list comprehension like `[ x:xs | x <- m, xs <- m' ]`.
camccann
+1  A: 

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.

BleuM937
It's the same as sclv's, in fact, up to a few differences in syntax. Also, you know this (having written the translation), but for anyone else: note that Eric Lippert's example uses a *left* fold instead of a right fold, but this makes no difference because the function is strict in the spines of the lists anyway (as with `sequence` in general).
camccann
+1  A: 

If you want to have more control over the output, you can use a list as applicative functor, e.g.:

(\x y z -> [x,y,­z]) <$>  [1,2]­ <*> [4,5]­ <*> [6,7]

Let's say you want a list of tuples instead:

(\x y z -> (x,y,­z)) <$>  [1,2]­ <*> [4,5]­ <*> [6,7]

And it looks kind of cool, too...

Landei