Haskell中2个列表的笛卡尔积

Question

我希望在Haskell中生成2个列表的笛卡尔积,但我无法弄清楚如何做到这一点.笛卡尔积给出了列表元素的所有组合:

xs = [1,2,3]
ys = [4,5,6]

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys ==> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

这不是一个实际的家庭作业问题,与任何此类问题无关,但解决这个问题的方式可能有助于我坚持下去.

Answer 1

列表推导这很容易.要获取列表的笛卡儿积xs和ys,我们只需要把元组(x,y)的每个元素x中xs,每个元素y中ys.

这给了我们以下列表理解:

cartProd xs ys = [(x,y) | x <- xs, y <- ys]

Answer 2

正如其他答案所指出的那样,使用列表推导是在Haskell中执行此操作的最自然的方法.

如果你正在学习Haskell并希望开发关于类型类的直觉Monad,那么,这是一个有趣的练习,可以找出为什么这个稍微短一些的定义是等价的:

import Control.Monad (liftM2)

cartProd :: [a] -> [b] -> [(a, b)]
cartProd = liftM2 (,)

你可能不会想要在实际代码中写这个,但基本的想法是你一直在Haskell中看到的东西:我们liftM2用来将非monadic函数提升(,)为monad - 在这种情况下特别是列出monad.

如果这没有任何意义或没有用,请忘记它 - 这只是另一种看待问题的方法.

Answer 3

如果您的输入列表属于同一类型,则可以使用sequence(使用Listmonad)获取任意数量列表的笛卡尔积.这将为您提供列表而不是元组列表:

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

Answer 4

使用Applicative Functors有一种非常优雅的方法:

import Control.Applicative

(,) <$> [1,2,3] <*> [4,5,6]
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

基本思想是在"包装"参数上应用函数,例如

(+) <$> (Just 4) <*> (Just 10)
-- Just 14

在列表的情况下,该函数将应用于所有组合,因此您所要做的就是用它们"元组化"它们(,).

见http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors或(更多的理论)http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf为细节.

Answer 5

其他答案假设两个输入列表是有限的.通常,惯用的Haskell代码包含无限列表,因此有必要简要评论如何在需要时生成无限笛卡尔积.

标准方法是使用对角化; 在顶部写一个输入,在左边写另一个输入,我们可以编写一个包含完整笛卡尔积的二维表,如下所示:

   1  2  3  4 ...
a a1 a2 a3 a4 ...
b b1 b2 b3 b4 ...
c c1 c2 c3 c4 ...
d d1 d2 d3 d4 ...

.  .  .  .  . .
.  .  .  .  .  .
.  .  .  .  .   .

当然,在任何一行中工作都会在到达下一行之前为我们提供无限元素; 同样地按柱式进行将是灾难性的.但是我们可以沿着向下和向左的对角线前进,每当我们到达网格的边缘时再向右开始.

a1

   a2
b1

      a3
   b2
c1

         a4
      b3
   c2
d1

...等等.按顺序,这会给我们:

a1 a2 b1 a3 b2 c1 a4 b3 c2 d1 ...

要在Haskell中对此进行编码,我们可以先编写生成二维表的版本:

cartesian2d :: [a] -> [b] -> [[(a, b)]]
cartesian2d as bs = [[(a, b) | a <- as] | b <- bs]

对角化的低效方法是首先沿对角线迭代然后沿每个对角线的深度迭代,每次拉出适当的元素.为了简化说明,我假设输入列表都是无限的,所以我们不必乱用边界检查.

diagonalBad :: [[a]] -> [a]
diagonalBad xs =
    [ xs !! row !! col
    | diagonal <- [0..]
    , depth <- [0..diagonal]
    , let row = depth
          col = diagonal - depth
    ]

这个实现有点不幸:重复列表索引操作!!变得越来越昂贵,给出了相当糟糕的渐近性能.更有效的实现将采用上述想法,但使用拉链实现它.所以,我们将无限网格划分为三个这样的形状:

a1 a2 / a3 a4 ...
     /
    /
b1 / b2 b3 b4 ...
  /
 /
/
c1 c2 c3 c4 ...
---------------------------------
d1 d2 d3 d4 ...

 .  .  .  . .
 .  .  .  .  .
 .  .  .  .   .

左上角的三角形将是我们已经发出的位; 右上四边形将是已经部分发射但仍会对结果有贡献的行; 底部矩形将是我们尚未开始发射的行.首先,上三角形和上四边形将为空,底部矩形将是整个网格.在每一步,我们可以发出上四边形中每行的第一个元素(基本上将斜线移动一个),然后从底部矩形向上四边形添加一个新行(基本上将水平线向下移动一个) ).

diagonal :: [[a]] -> [a]
diagonal = go [] where
    go upper lower = [h | h:_ <- upper] ++ case lower of
        []         -> concat (transpose upper')
        row:lower' -> go (row:upper') lower'
        where upper' = [t | _:t <- upper]

虽然这看起来有点复杂,但效率要高得多.它还处理我们在更简单的版本中处理的边界检查.

但是你当然不应该自己编写所有这些代码!相反,您应该使用Universe包.在Data.Universe.Helpers,有(+*+),将上述cartesian2d和diagonal功能打包在一起,只提供笛卡尔积的操作:

Data.Universe.Helpers> "abcd" +*+ [1..4]
[('a',1),('a',2),('b',1),('a',3),('b',2),('c',1),('a',4),('b',3),('c',2),('d',1),('b',4),('c',3),('d',2),('c',4),('d',3),('d',4)]

如果该结构变得有用,您还可以看到对角线本身:

Data.Universe.Helpers> mapM_ print . diagonals $ cartesian2d "abcd" [1..4]
[('a',1)]
[('a',2),('b',1)]
[('a',3),('b',2),('c',1)]
[('a',4),('b',3),('c',2),('d',1)]
[('b',4),('c',3),('d',2)]
[('c',4),('d',3)]
[('d',4)]

如果您有许多列表可以一起产品,迭代(+*+)会不公平地偏向某些列表; 您可以使用choices :: [[a]] -> [[a]]您的n维笛卡尔产品需求.

Answer 6

正如其他人已经指出的那样,正确的方法是使用列表推导,但如果你想在没有使用列表推导的情况下出于任何原因这样做,那么你可以这样做:

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs [] = []
cartProd [] ys = []
cartProd (x:xs) ys = map (\y -> (x,y)) ys ++ cartProd xs ys

Answer 7

另一种方式,使用do符号:

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = do x <- xs
                    y <- ys
                    return (x,y)

Answer 8

另一种实现此目的的方法是使用applicatives:

import Control.Applicative

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = (,) <$> xs <*> ys

Answer 9

好吧,一个非常简单的方法是使用列表推导:

cartProd :: [a] -> [b] -> [(a, b)]
cartProd xs ys = [(x, y) | x <- xs, y <- ys]

我想我是怎么做到的,虽然我不是Haskell专家(无论如何).

Answer 10

就像是:

cartProd x y = [(a,b) | a <- x, b <- y]