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 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]]

[]