Haskell: cartesian product of a list with itself n times

user_6117426 0
Viewed 120

What's a simple way of computing the cartesian product of a list with itself n times?

That is, how can I define the function cartesianExp :: Int -> [a] -> [[a]].

For instance, the cartesian product of [1,2] with itself 3 times (n = 3) should be:

[
 [1, 1, 1],
 [1, 1, 2],
 [1, 2, 1],
 [1, 2, 2],
 [2, 1, 1],
 [2, 1, 2],
 [2, 2, 1],
 [2, 2, 2]
]
haskell
2 Answers

You can work with replicateM :: Applicative f => Int -> f a -> f [a] to do this. Indeed:

ghci> import Control.Monad(replicateM)
ghci> replicateM 0 "abc"
[""]
ghci> replicateM 1 "abc"
["a","b","c"]
ghci> replicateM 2 "abc"
["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
ghci> replicateM 3 "abc"
["aaa","aab","aac","aba","abb","abc","aca","acb","acc","baa","bab","bac","bba","bbb","bbc","bca","bcb","bcc","caa","cab","cac","cba","cbb","cbc","cca","ccb","ccc"]
ghci> replicateM 3 [1,2]
[[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]
user_675790 
import Data.List


cartesianExp :: Int -> [a] -> [[a]]
cartesianExp 0 _ = [[]]
cartesianExp n xs = [x:tup | x <- xs, tup <- cartesianExp (n - 1) xs]

By convention, the cartesian product of a set S with itself 0 times, S0, is the set consisting of a single empty tuple.

Then, the cartesian product of a set S with itself n times, Sn, can be defined inductively by expanding each of the tuples in Sn-1 by each of the elements in S.

(Here I'm using the mathematical meaning of the terms set and tuple, in the Haskell implementation they both correspond to lists in this case.)

user_61174260
Related