Haskell:列表与自身n次的笛卡尔积

Question

计算列表与自身的笛卡尔积n的简单方法是什么?

即如何定义函数cartesianExp :: Int -> [a] -> [[a]]。

例如，[1,2]与自身的笛卡尔积(n = 3)应为:

[
[1, 1, 1],
[1, 1, 2],
[1, 2, 1],
[1, 2, 2],
[2, 1, 1],
[2, 1, 2],
[2, 2, 1],
[2, 2, 2]
]

Answer 1

您可以使用replicateM :: Applicative f => Int -> f a -> f [a]来做这个。事实上:

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

Answer 2

import Data.List

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

根据约定，集合S与自身0次的笛卡尔积S⁰是由单个空元组组成的集合。

那么，集合S与自身n倍的笛卡尔积Sⁿ，可以通过将S^n-1中的每个元素展开S中的每个元素来归纳定义。

(这里我使用了术语set和tuple的数学含义，在Haskell实现中，它们在这种情况下都对应于列表)