计算n元笛卡儿积

Question

给定两个列表,我可以生成这两个列表的笛卡尔积的所有排列的列表:

permute :: [a] -> [a] -> [[a]]
permute xs ys = [ [x, y] | x <- xs, y <- ys ]

Example> permute [1,2] [3,4] == [ [1,3], [1,4], [2,3], [2,4] ]

如何扩展置换,以便不使用两个列表,而是获取列表的列表(长度为n)并返回列表列表(长度为n)

permute :: [[a]] -> [[a]]

Example> permute [ [1,2], [3,4], [5,6] ]
            == [ [1,3,5], [1,3,6], [1,4,5], [1,4,6] ] --etc

我在Hoogle上找不到任何相关的东西..唯一与签名相匹配的功能是transpose,它不会产生所需的输出.

编辑:我认为这个2列表版本基本上是笛卡尔积,但我不能完全实现n-ary笛卡尔积.有什么指针吗？

Answer 1

Prelude> sequence [[1,2],[3,4],[5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]

Answer 2

我发现 Eric Lippert 关于使用 LINQ 计算笛卡尔积的文章对提高我对正在发生的事情的理解非常有帮助。这是或多或少的直接翻译：

cartesianProduct :: [[a]] -> [[a]]
cartesianProduct sequences = foldr aggregator [[]] sequences
                   where aggregator sequence accumulator = 
                         [ item:accseq |item <- sequence, accseq <- accumulator ]

或者使用更多“Haskell-y”简洁、无意义的参数名称；)

cartesianProduct = foldr f [[]]
                    where f l a = [ x:xs | x <- l, xs <- a ]

毕竟这与发布的 sclv 非常相似。

Answer 3

这是我简单地实现它的方法，仅使用列表理解。

crossProduct :: [[a]] -> [[a]]
crossProduct (axis:[]) = [ [v] | v <- axis ]
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ]