Cartesian product of two or more lists
- 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 sequence function to a list of lists:
<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]] []