哈斯克尔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 提高非弥补功能 (,) 进入单子 - 在这种情况下，特别是清单单。

如果这没有任何意义或没有用，那就算了 - 这只是查看问题的另一种方式。

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

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 有关详细信息。

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]

尽管这看起来更复杂，但效率更高。它还处理了我们在简单版本中刺穿的界限检查。

但是，您当然不应该自己编写所有这些代码！相反，您应该使用 宇宙 包裹。在 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

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

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]

Answer 11

这是一项工作 sequenceing。它的单一实施可能是：

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

Answer 12

这是我对N- ARY笛卡尔产品的实施：

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

Answer 13

仅使用递归图案匹配，只需为发烧友添加一种方式即可。

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