CODEWITHSUNDEEP
haskellfunctional-programmingcombinatoricscartesian-product
Caridorc
Caridorc

Reputation: 6641

Cartesian product over a list of lists in Haskell

Given a list of lists of length x where all the sublists have the same length y, output the y^x lists of length x that contain one item from each sublist.

Example (x = 3, y = 2):

[ [1, 2], [3, 4], [5, 6] ]

Output (2^3 == 8 different outputs):

[ [1, 3, 5], [1, 4, 5], [1, 3, 6], [1, 4, 6],
  [2, 3, 5], [2, 4, 5], [2, 3, 6], [2, 4, 6] ]

My research / Work

Ruby

I wrote actual code to perform this task, but in Ruby, as it is the language I am most comfortable with.

def all_combinations(lst)
   lst.inject {|acc, new| acc.product(new).map(&:flatten) }
end

Type

Input is a list of lists that contains items of type a and so is the output.

allProduct :: [[a]] -> [[a]]

Cartesian product, flattening and folding

Looking at my Ruby solution makes me think that a good use of these functions may be enough to solve the problem. The problem is that while the Cartesian Product outputs a list of tuples but I need a list of lists.

Upvotes: 5

Views: 2017

Answers (1)

Zeta
Zeta

Reputation: 105876

Note: This post is written in literate Haskell. Save it as *.lhs and load it in GHCi.

> -- remove this line if you don't have QuickCheck installed
> import Test.QuickCheck

A simple recursive variant

Lets start with a simple variant of allProduct:

> allProductFirst :: [[a]] -> [[a]]
> allProductFirst []     = [[]]
> allProductFirst (x:xs) =

Now x itself is a list again. Let's say that allProduct xs would give us the product of the other lists.

>    let rest = allProductFirst xs

What do we need to do? We need to create a new list for every element in x and concat them together:

>    in concatMap (\k -> map (k:) rest) x

Note that this variant isn't 100% correct, as allProduct [] is [[]].

A monadic variant

How would this look like if we were to use the Monad instance of []?

Using do notation

> allProduct' :: [[a]] -> [[a]]
> allProduct' []     = [[]]
> allProduct' (x:xs) = do

We want to take every element of x

>      elementOfX <- x

and cons it onto all the possible suffixes our list can have:

>      rest       <- allProduct' xs
>      return $ elementOfX : rest

This means we're basically evaluation every action inside our list monad. But there's a function for that: sequence :: Monad m => [m a] -> m [a]. If we use m ~ [], its type can be specialized to sequence :: [[a]] -> [[a]].

Using sequence

We end up with our last variant:

> allProduct :: [[a]] -> [[a]]
> allProduct = sequence

Testing the result

We use QuickCheck to test that it's likely the same as allProductFirst and allProduct':

> main :: IO ()
> main = do
>   quickCheck $
>     forAll (choose (1,8)) $ \n -> -- number of lists
>     forAll (choose (1,4)) $ \s -> -- number of elements per list
>     forAll (vectorOf n $ vector s) $ \xs ->
>       allProduct'     xs === allProduct (xs :: [[Integer]]) .&.
>       allProductFirst xs === allProduct xs

Use :main in GHCi, runhaskell or compile and run your program, and you should end up with 100 passed tests.

Upvotes: 14

Related Questions