计算n元笛卡尔积

Question

给定两个列表，我可以产生这两个列表的Cartesian积：

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

如何扩展permute，使其不再接受两个列表，而是接受一个长为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元笛卡尔积。有什么建议吗？

- guhou

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

- Josh Lee

---

虽然序列确实解决了问题，但我真的很想知道这是如何工作的。实现使用了单子；是否有一种不使用单子（例如在不包括单子的语言中）计算乘积的方法？ - guhou

@BleuM937：对于列表单子，sequence 的意思是“对于第一个列表中的每个元素，在剩余列表上进行序列化并将其添加到每个列表的开头”。基本上，这是使用右折叠写笛卡尔积的最明显的方法。 - C. A. McCann

如果你告诉我们具体是如何工作的，我会点赞这个。 - SWdV

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发布的内容非常相似。

- guhou

---

实际上，除了一些语法上的差异外，它与sclv的代码是相同的。此外，您已经知道这一点（因为您编写了翻译），但对于其他人来说，请注意Eric Lippert的示例使用左折叠而不是右折叠，但这没有任何区别，因为该函数在列表的脊柱中是严格的（与sequence一般情况下相同）。 - C. A. McCann

Answer 3

这是我使用列表推导式简单实现它的方法，仅使用列表推导式。

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

- Christian Oudard

Answer 4

作为jleedev回答的补充（在评论中无法格式化此内容）：

将列表函数快速替换为单子函数的未经检查的方式：

sequence ms = foldr k (return []) ms
   where
    k m m' = do { x <- m; xs <- m'; return (x:xs) }

....

    k m m' = m >>= \x -> m' >>= \xs -> [x:xs]
    k m m' = flip concatMap m $ \x -> flip concatMap m' $ \xs -> [x:xs]
    k m m' = concatMap (\x -> concatMap (\xs -> [x:xs]) m') m

....

sequence ms = foldr k ([[]]) ms
   where
     k m m' = concatMap (\x -> concatMap (\xs -> [x:xs]) m') m

- sclv

---

可以通过在 k m m' = concatMap (\x -> map (x:) m') m 中消除一个多余的连接符来进一步简化它。也可以像 [ x:xs | x <- m, xs <- m' ] 这样使用列表推导式来表示。请注意，这两种写法的意思相同，只是表达方式不同。 - C. A. McCann

Answer 5

如果你想更加掌握输出的控制，你可以使用一个列表作为适用函子，例如：

(\x y z -> [x,y,­z]) <$>  [1,2]­ <*> [4,5]­ <*> [6,7]

假设您需要一个元组列表：

(\x y z -> (x,y,­z)) <$>  [1,2]­ <*> [4,5]­ <*> [6,7]

而且它看起来也很酷...

- Landei

Answer 6

你可以用两种方法来实现这个：

1. 使用列表推导式

  cp :: [[a]] -> [[a]]
  cp []       = [[]]
  cp (xs:xss) = [ x:ys | x <- xs, ys <- cp xss ]

使用折叠功能

  cp1 :: [[a]] -> [[a]]
  cp1 xs = foldr f [[]] xs
        where f xs xss = [x:ys | x <- xs, ys <- xss]

- Andrei Draghici