计算n元笛卡尔乘积

鉴于两份名单，我可以生产 ~~所有排列的列表~~ 这两个列表的笛卡尔乘积：计算n元笛卡尔乘积

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列表版本本质上是Cartesian Product，但我无法围绕实施n-ary Cartesian Product包裹我的头。任何指针？

来源

2010-08-02 guhou

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

来源

2010-08-02 11:55:55

虽然序列不含解决亲嗯，我真的很感兴趣，这将如何工作。 [实施]（http://haskell.org/ghc/docs/6.12.1/html/libraries/base-4.2.0.0/src/Control-Monad.html#sequence）使用单子;有没有一种方法可以在不使用monads的情况下计算产品？（例如，不包含单子的语言） – guhou 2010-08-02 12:18:37

@ BleuM937：对于monad列表，“sequence”的意思是“对于第一个列表中的每个元素，将其预先加入到通过排序剩余列表而获得的每个列表中”。这基本上是使用正确折叠编写笛卡尔产品的最明显方式。 – 2010-08-02 13:52:52

为补充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

来源

2010-08-02 12:36:49 sclv

通过消除'k m m'= concatMap（\ x - > map（x :) m'）m'中的多余级联，可以进一步简化该操作。也可以将它写成列表理解，如'[x：xs | x < - m，xs < - m']'。 – 2010-08-02 13:46:46

我发现Eric Lippert在computing Cartesian product with LINQ上的文章对提高我对正在发生的事情的理解很有帮助。这里有一个更多或更少的直接翻译：

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

或者更多的“哈斯克尔-Y”简洁，毫无意义的参数名称;）

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

这卷起是相当类似sclv张贴毕竟。

来源

2010-08-02 14:30:29 guhou

这和sclv的一样，实际上，在语法上有一些差异。另外，你知道这一点（写过翻译），但是对于其他人：请注意，Eric Lippert的例子使用* left * fold而不是右对齐，但这没有什么区别，因为函数在列表的刺无论如何（就像'一般'序列一样）。 – 2010-08-02 15:55:03

如果你想拥有对输出更多的控制，你可以使用列表作为适用函子，如：

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

比方说，你想一个元组的列表，而不是：

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

它看起来也很酷...

来源

2010-08-03 12:05:13 Landei

这里是我简单地实施它的方式，只使用列表解析。

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

来源

2016-04-12 17:37:10

你可以在2种方式：

使用列表理解

CP :: [[A] - > [一]

cp [] = [[]]

cp（xs：xss）= [x：ys | X < - XS，YS < - CP XSS]

使用折叠

CP1 :: [[α]] - > [[一]

CP1 XS = foldr相似F [[]] XS
where f xs xss = [x:ys | x <- xs, ys <- xss] 

来源

2017-11-13 14:48:48

计算n元笛卡尔乘积

回答

相关问题