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

CodePudding user response：

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

CodePudding user response：

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, S⁰, is the set consisting of a single empty tuple.

Then, the cartesian product of a set S with itself n times, Sⁿ, can be defined inductively by expanding each of the tuples in S^n-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.)