Haskell 中 2 个列表的笛卡尔积

13 回答

• 6

  好吧，一种很简单的方法就是列表理解：

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

  尽管我不是 Haskell 专家(无论如何)，但我想是如何做到的。

  回复于 2024-04-25T20:23:42+08:00
• 5

  就像是：

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

  回复于 2024-04-25T20:23:42+08:00
• 11

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

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

  回复于 2024-04-25T20:23:42+08:00
• 11

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

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

  回复于 2024-04-25T20:23:42+08:00
• 100

  列表理解非常简单。要获得列表xs和ys的笛卡尔积，我们只需要对xs中的每个元素x和ys中的每个元素y取元组(x,y)即可。

  这使我们可以理解以下列表：

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

  回复于 2024-04-25T20:23:42+08:00
• 62

  正如其他答案所指出的那样，在 Haskell 中使用列表理解是最自然的方法。

  但是，如果您正在学习 Haskell 并想开发有关诸如Monad之类的类型类的直觉，那么弄清楚为什么这个略短的定义是等效的是一个有趣的练习：

  import Control.Monad (liftM2)
  
  cartProd :: [a] -> [b] -> [(a, b)]
  cartProd = liftM2 (,)
  

  您可能永远不想用真实的代码编写此代码，但是基本的想法是您始终会在 Haskell 中看到的东西：我们使用liftM2将 non-monadic 函数(,)提升为 monad，在这种情况下，特别是列出单子。

  如果这没有任何意义或没有用，请忘记它-这只是解决问题的另一种方法。

  回复于 2024-04-25T20:23:42+08:00
• 52

  如果输入列表属于同一类型，则可以使用sequence(使用List monad)获得任意数量的列表的笛卡尔积。这将为您提供列表列表，而不是元组列表：

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

  回复于 2024-04-25T20:23:42+08:00
• 45

  应用函子有一个非常优雅的方法：

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

  基本思想是对“包装的”参数 e.g 应用一个函数。

  (+) <$> (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。

  回复于 2024-04-25T20:23:42+08:00
• 14

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

  标准方法是使用对角线化。在顶部写一个输入，在左边写另一个输入，我们可以编写一个 two-dimensional 表，其中包含完整的笛卡尔积，如下所示：

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

  当然，跨任何一行工作都会在到达下一行之前为我们提供无限的元素；同样地 column-wise 将是灾难性的。但是，我们可以沿着向下和向左向下的对角线移动，每次到达网格的边缘时，都从右向右开始一点。

  a1
  
     a2
  b1
  
        a3
     b2
  c1
  
           a4
        b3
     c2
  d1
  

  ...and 依此类推。为了使我们能够：

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

  要在 Haskell 中对此进行编码，我们首先可以编写产生 two-dimensional 表的版本：

  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-dimensional 笛卡尔积。

  回复于 2024-04-25T20:23:42+08:00
• 11

  正如其他人已经指出的那样，正确的方法是使用列表推导，但是如果您出于某种原因不想使用列表推导，则可以这样做：

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

  回复于 2024-04-25T20:23:42+08:00
• 2

  这是sequence ing 的工作。它的单例实现可以是：

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

  回复于 2024-04-25T20:23:42+08:00
• 0

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

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

  回复于 2024-04-25T20:23:42+08:00
• 0

  仅使用递归模式匹配为发烧友增加另一种方式。

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

  回复于 2024-04-25T20:23:42+08:00