12

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

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-list 版本本质上是Cartesian Product,但我无法实现n-ary Cartesian Product。任何指针?

4

6 回答 6

22
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-02T11:55:55.737 回答
6

我发现 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 非常相似。

于 2010-08-02T14:30:29.493 回答
4

这是我简单地实现它的方法,只使用列表推导。

crossProduct :: [[a]] -> [[a]]
crossProduct (axis:[]) = [ [v] | v <- axis ]
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ]
于 2016-04-12T17:37:10.130 回答
3

作为 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-02T12:36:49.053 回答
2

如果您想更好地控制输出,可以使用列表作为应用函子,例如:

(\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-03T12:05:13.620 回答
1

您可以通过 2 种方式执行此操作:

  1. 使用列表理解
  cp :: [[a]] -> [[a]]
  cp []       = [[]]
  cp (xs:xss) = [ x:ys | x <- xs, ys <- cp xss ]
  1. 使用折叠
  cp1 :: [[a]] -> [[a]]
  cp1 xs = foldr f [[]] xs
        where f xs xss = [x:ys | x <- xs, ys <- xss]
于 2017-11-13T14:48:48.757 回答