Haskell中两个列表的笛卡尔积

Question

我希望在Haskell中生成两个列表的笛卡尔积，但我不知道该如何实现。笛卡尔积会给出列表元素的所有组合:

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

这不是一道真正的作业问题，也与任何此类问题无关，但解决这个问题的方法可能有助于我卡住的一个问题。

- Callum Rogers

---

相关问题：Haskell中无限列表的笛卡尔积。 - Will Ness

Answer 1

这很容易使用列表推导式来实现。要获取列表 xs 和 ys 的笛卡尔积，我们只需要为每个元素 x 在 xs 中以及每个元素 y 在 ys 中取元组 (x,y)。

这给出了以下列表推导式：

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

- sepp2k

---

谢谢，如此简单而优雅，真的帮助了我解决其他问题 :) - Callum Rogers

也适用于Erlang，谢谢。语法稍有改变： cartProd(Xs, Ys) -> [{X,Y} || X <- Xs, Y <- Ys]。 - Dacav

Answer 2

正如其他答案所述，在Haskell中使用列表推导是最自然的方法。

但如果你正在学习Haskell并希望培养类别（例如Monad）的直觉，那么尝试理解这个略微缩短的定义等价的原因是一种有趣的练习：

import Control.Monad (liftM2)

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

你可能不会在实际代码中编写这个，但基本思想是Haskell中经常使用的：我们使用liftM2将非单子函数(,)提升到单子中——在这种情况下，特别是列表单子。

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

- Travis Brown

---

最好先了解一下单子的实际作用。:P - Callum Rogers

作为一条脚注（三年后）：我现在猜测，当时我最初在这里使用单子的liftM2是出于清晰易懂的考虑（更多人听说过单子而不是应用函子？），但你只需要列表的应用函子实例，所以liftA2同样可行。 - Travis Brown

Answer 3

如果您的输入列表类型相同，则可以使用sequence（使用List单子）获取任意数量列表的笛卡尔积。这将为您提供一个列表而不是元组列表：

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

- newacct

Answer 4

有一种非常优雅的方式可以使用应用函子来实现：

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。

- Landei

---

很不错，你实际上可以根据需要扩展元组：(,,) <$> [1..3] <*> [4..6] <*> [7..9]。 - Landon Poch

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

- Daniel Wagner

---

我刚刚安装了Universe-1.1，它太棒了。非常感谢你。是的，你的名字无处不在，所以我们知道可以信任它。价值是无法计算的。我正在进行对角线操作，这些初始结果看起来非常准确。笛卡尔积很麻烦，但你就像止痛药一样。再次感谢你。 - fp_mora

@fp_mora 很高兴听到你喜欢它！ - Daniel Wagner

@Daniel Wagner 这真是太好了。我之前不是很清楚，无限列表确实很麻烦。但你处理得非常娴熟。 - fp_mora

Answer 6

另一种实现这个目的的方法是使用 applicatives：

import Control.Applicative

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

- Paul

Answer 7

另一种方式是使用 do 表示法：

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

- gawi

Answer 8

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

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

- Stuart Golodetz

---

一个不使用列表推导的更简单的方法是 cartProd xs ys = xs >>= \x -> ys >>= \y -> [(x,y)]。这行代码的意思是，对于给定的两个列表 xs 和 ys，将它们的所有元素依次配对，并返回一个由这些配对组成的新列表。 - Chuck

你可以使用 map ((,) x) 替换 map (\y -> (x,y))。 - Yitz

@Chuck：很好 :) 对我来说已经有一段时间没有接触Haskell了，这就是为什么我更倾向于简单的解决方案... - Stuart Golodetz

@Yitz：没错，说得好。我忘记了那个（请参见上面的“已经有一段时间了”）... - Stuart Golodetz

@Stuart 列表推导式可能是“正确的方法”，但用这种方式真的有什么缺点吗？ 在我看来，这很好，并且它有助于初学者理解笛卡尔积的简单实现。+1 - Landon Poch

@Stuart 我猜这个实现的问题可能在于如果你需要取三个或更多列表的乘积，那么如何展平它。我可以看到这里有一个单子的提示。 - Landon Poch

Answer 9

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

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

我认为这是我会做的方法，虽然我不是Haskell专家（绝非如此）。

- James Cunningham

Answer 10

something like:

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

- vichle