79

我希望在 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)]

这不是一个实际的家庭作业问题，也与任何此类问题无关，但解决此问题的方式可能对我遇到的问题有所帮助。

4

14 回答 14

129

这对于列表推导非常容易。要获得列表xs和的笛卡尔积ys，我们只需要获取 中的(x,y)每个元素和x中的每个元素的元组。xsyys

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

cartProd xs ys = [(x,y) | x <- xs, y <- ys]
于 2010-11-07T21:20:46.957 回答
79

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

但是，如果您正在学习 Haskell 并想致力于开发有关类型类的直觉，Monad例如

import Control.Monad (liftM2)

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

你可能永远不想用真正的代码来写这个，但基本的想法是你会在 Haskell 中看到的东西：我们liftM2用来将非单子函数提升(,)为单子——在这种情况下，特别是列出单子。

如果这没有任何意义或没有用，那就忘记它——这只是看待问题的另一种方式。

于 2010-11-07T21:52:58.937 回答
62

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]]
于 2010-11-07T22:58:30.903 回答
53

使用 Applicative Functor 有一种非常优雅的方法：

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细节。

于 2010-11-08T08:06:40.110 回答
18

其他答案假设两个输入列表是有限的。通常，惯用的 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
    ]

这个实现有点不幸：重复的列表索引操作!!变得越来越昂贵，渐近性能很差。更有效的实现将采用上述想法，但使用 zippers 实现它。因此，我们将无限网格划分为三个形状，如下所示：

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 维笛卡尔积需求。

于 2017-10-24T01:21:48.697 回答
16

实现此目的的另一种方法是使用应用程序：

import Control.Applicative

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = (,) <$> xs <*> ys
于 2010-11-08T03:11:59.987 回答
15

还有另一种方式，使用do符号：

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = do x <- xs
                    y <- ys
                    return (x,y)
于 2010-11-08T01:30:53.517 回答
12

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

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs [] = []
cartProd [] ys = []
cartProd (x:xs) ys = map (\y -> (x,y)) ys ++ cartProd xs ys
于 2010-11-07T21:30:09.933 回答
6

好吧，一种非常简单的方法是使用列表推导：

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

我想我会怎么做，虽然我不是 Haskell 专家（无论如何）。

于 2010-11-07T21:20:49.140 回答
6

就像是：

cartProd x y = [(a,b) | a <- x, b <- y]
于 2010-11-07T21:21:02.133 回答
4

这是一份工作sequence。它的一元实现可能是：

cartesian :: [[a]] -> [[a]]
cartesian [] = return []
cartesian (x:xs) = x >>= \x' -> cartesian xs >>= \xs' -> return (x':xs')

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

正如您可能注意到的，上面的实现类似于map纯函数的实现，但是是单子类型。因此，您可以将其简化为

cartesian :: [[a]] -> [[a]]
cartesian = mapM id

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
于 2017-05-08T19:54:24.763 回答
0

这是我对 n 元笛卡尔积的实现：

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

只是为发烧友增加了一种方式，只使用递归模式匹配。

cartProd :: [a]->[b]->[(a,b)]
cartProd _ []=[]
cartProd [] _ = []
cartProd (x:xs) (y:ys) = [(x,y)] ++ cartProd [x] ys  ++ cartProd xs ys ++  cartProd xs [y]
于 2018-09-25T10:12:13.947 回答
0

没有列表理解的递归模式匹配

crossProduct [] b=[]
crossProduct (x : xs) b= [(x,b)] ++ crossProduct xs b

cartProd _ []=[]
cartProd x (u:uv) = crossProduct x u ++ cartProd x uv
于 2019-11-17T02:24:22.310 回答