Cartesian product of two or more lists

Cartesian product of two or more lists is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

Show one or more idiomatic ways of generating the Cartesian product of two arbitrary lists in your language.

Demonstrate that your function/method correctly returns:

{1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}

and, in contrast:

{3,4} × {1,2} = {(3,1), (3,2), (4,1), (4,2)}

Also demonstrate, using your function/method, that the product of an empty list with any other list is empty.

{1,2} × {} = {}

{} × {1,2} = {}

For extra credit, show or write a function returning the n-ary product of an arbitrary number of lists, each of arbitrary length. Your function might, for example, accept a single argument which is itself a list of lists, and return the n-ary product of those lists.

Use your n-ary Cartesian product function to show the following products:

{1776, 1789} × {7,12} × {4, 14, 23} × {0, 1}}

{1,2,3} × {30} × {500, 100}

{1,2,3} × {} × {500, 100}

Haskell

Various routes can be taken to Cartesian products in Haskell. For the product of two lists we could write: <lang Haskell>cartProd :: [a] -> [a] -> [(a, a)] cartProd xs ys =

 [ (x, y)
 | x <- xs 
 , y <- ys ]</lang>

Or, more directly: <lang Haskell>cartProd :: [a] -> [a] -> [(a, a)] cartProd xs ys = xs >>= \x -> ys >>= \y -> [(x, y)]</lang>

We might test either of these with: <lang haskell>main :: IO () main =

 mapM_ print $
 uncurry cartProd <$>
 [([1, 2], [3, 4]), ([3, 4], [1, 2]), ([1, 2], []), ([], [1, 2])]</lang>

Output:

[(1,3),(1,4),(2,3),(2,4)]
[(3,1),(3,2),(4,1),(4,2)]
[]
[]

For the n-ary Cartesian product of an arbitrary number of lists, we could apply the Prelude's standard sequence function to a list of lists, or we could define ourselves an equivalent function over a list of lists in terms of a fold:

For example as: <lang haskell>foldr (\xs as -> xs >>= \x -> as >>= \a -> [x : a]) [[]]</lang> or, equivalently, as: <lang haskell>foldr

   (\xs as ->
       [ x : a
       | x <- xs
       , a <- as ])
   [[]]</lang>

<lang haskell>main :: IO () main = do

 mapM_ print $ 
   sequence [[1776, 1789], [7,12], [4, 14, 23], [0,1]]
 putStrLn ""
 print $ sequence [[1,2,3], [30], [500, 100]]
 putStrLn ""
 print $ sequence [[1,2,3], [], [500, 100]]</lang>

Output:

[1776,7,4,0]
[1776,7,4,1]
[1776,7,14,0]
[1776,7,14,1]
[1776,7,23,0]
[1776,7,23,1]
[1776,12,4,0]
[1776,12,4,1]
[1776,12,14,0]
[1776,12,14,1]
[1776,12,23,0]
[1776,12,23,1]
[1789,7,4,0]
[1789,7,4,1]
[1789,7,14,0]
[1789,7,14,1]
[1789,7,23,0]
[1789,7,23,1]
[1789,12,4,0]
[1789,12,4,1]
[1789,12,14,0]
[1789,12,14,1]
[1789,12,23,0]
[1789,12,23,1]

[[1,30,500],[1,30,100],[2,30,500],[2,30,100],[3,30,500],[3,30,100]]

[]

JavaScript

ES6

For the Cartesian product of just two lists: <lang JavaScript>(() => {

   // CARTESIAN PRODUCT OF TWO LISTS -----------------------------------------

   // cartProd :: [a] -> [b] -> a, b
   const cartProd = (xs, ys) =>
       concatMap((x => concatMap(y => [
           [x, y]
       ], ys)), xs);

   // GENERIC FUNCTIONS ------------------------------------------------------

   // concatMap :: (a -> [b]) -> [a] -> [b]
   const concatMap = (f, xs) => [].concat.apply([], xs.map(f));

   // map :: (a -> b) -> [a] -> [b]
   const map = (f, xs) => xs.map(f);

   // show :: a -> String
   const show = x => JSON.stringify(x); //, null, 2);

   // unlines :: [String] -> String
   const unlines = xs => xs.join('\n');

   // TEST -------------------------------------------------------------------
   return unlines(map(show, [
       cartProd([1, 2], [3, 4]),
       cartProd([3, 4], [1, 2]),
       cartProd([1, 2], []),
       cartProd([], [1, 2]),
   ]));

})();</lang>

Output:

[[1,3],[1,4],[2,3],[2,4]]
[[3,1],[3,2],[4,1],[4,2]]
[]
[]

For the n-ary Cartesian product over a list of lists: <lang JavaScript>(() => {

   // n-ary Cartesian product of a list of lists

   // cartProdN :: a -> a
   const cartProdN = lists =>
       foldr((xs, as) =>
           bind(xs, x => bind(as, a => [x.concat(a)])), [
               []
           ], lists);

   // GENERIC FUNCTIONS ------------------------------------------------------

   // concatMap ::  [a] -> (a -> [b]) -> [b]
   const bind = (xs, f) => [].concat.apply([], xs.map(f));

   // foldr (a -> b -> b) -> b -> [a] -> b
   const foldr = (f, a, xs) => xs.reduceRight(f, a);

   // intercalate :: String -> [a] -> String
   const intercalate = (s, xs) => xs.join(s);

   // map :: (a -> b) -> [a] -> [b]
   const map = (f, xs) => xs.map(f);

   // show :: a -> String
   const show = x => JSON.stringify(x);

   // unlines :: [String] -> String
   const unlines = xs => xs.join('\n');

   return intercalate('\n\n', [unlines(map(show, cartProdN([
           [1776, 1789],
           [7, 12],
           [4, 14, 23],
           [0, 1]
       ]))),
       show(cartProdN([
           [1, 2, 3],
           [30],
           [50, 100]
       ])),
       show(cartProdN([
           [1, 2, 3],
           [],
           [50, 100]
       ]))
   ])

})();</lang>

Output:

[0,4,7,1776]
[0,4,7,1789]
[0,4,12,1776]
[0,4,12,1789]
[0,14,7,1776]
[0,14,7,1789]
[0,14,12,1776]
[0,14,12,1789]
[0,23,7,1776]
[0,23,7,1789]
[0,23,12,1776]
[0,23,12,1789]
[1,4,7,1776]
[1,4,7,1789]
[1,4,12,1776]
[1,4,12,1789]
[1,14,7,1776]
[1,14,7,1789]
[1,14,12,1776]
[1,14,12,1789]
[1,23,7,1776]
[1,23,7,1789]
[1,23,12,1776]
[1,23,12,1789]

[[50,30,1],[50,30,2],[50,30,3],[100,30,1],[100,30,2],[100,30,3]]

[]

Perl 6

Works with: Rakudo version 2017.05

Nominally the cross meta operator X does this, but doesn't gracefully handle the case of an empty list. We can easily wrap it in a subroutine with appropriate filtering however.

<lang perl6>sub cartesian-product (**@list) { ( so none(@list».elems) == 0 ) ?? [X] @list !! () }

1. Testing various Cartesian products

for

 ( (1, 2), (3, 4) ),
 ( (3, 4), (1, 2) ),
 ( (1, 2), ( ) ),
 ( ( ), ( 1, 2 ) ),
 ( (1776, 1789), (7, 12), (4, 14, 23), (0, 1) ),
 ( (1, 2, 3), (30), (500, 100) ),
 ( (1, 2, 3), (), (500, 100) )
 -> $list {
     say "\nLists: { $list.perl }\nCartesian Product:";
     say cartesian-product( |$list ).List.perl;
 }</lang>

Output:

Lists: $((1, 2), (3, 4))
Cartesian Product:
((1, 3), (1, 4), (2, 3), (2, 4))

Lists: $((3, 4), (1, 2))
Cartesian Product:
((3, 1), (3, 2), (4, 1), (4, 2))

Lists: $((1, 2), ())
Cartesian Product:
()

Lists: $((), (1, 2))
Cartesian Product:
()

Lists: $((1776, 1789), (7, 12), (4, 14, 23), (0, 1))
Cartesian Product:
((1776, 7, 4, 0), (1776, 7, 4, 1), (1776, 7, 14, 0), (1776, 7, 14, 1), (1776, 7, 23, 0), (1776, 7, 23, 1), (1776, 12, 4, 0), (1776, 12, 4, 1), (1776, 12, 14, 0), (1776, 12, 14, 1), (1776, 12, 23, 0), (1776, 12, 23, 1), (1789, 7, 4, 0), (1789, 7, 4, 1), (1789, 7, 14, 0), (1789, 7, 14, 1), (1789, 7, 23, 0), (1789, 7, 23, 1), (1789, 12, 4, 0), (1789, 12, 4, 1), (1789, 12, 14, 0), (1789, 12, 14, 1), (1789, 12, 23, 0), (1789, 12, 23, 1))

Lists: $((1, 2, 3), 30, (500, 100))
Cartesian Product:
((1, 30, 500), (1, 30, 100), (2, 30, 500), (2, 30, 100), (3, 30, 500), (3, 30, 100))

Lists: $((1, 2, 3), (), (500, 100))
Cartesian Product:
()