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

Question

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

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

例如[1,2]与其自身3次(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

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.

中的元素

（这里我使用术语集和元组的数学含义，在 Haskell 实现中它们都对应于这种情况下的列表。）

Answer 2

您可以使用 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]]

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

Haskell: cartesian product of a list with itself n times

haskell