Haskell中的2个列表的笛卡尔积

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

这不是一个真正的家庭作业问题,并不涉及任何这样的问题,但解决这个问题的方式可能有助于一个我坚持。

12 Solutions collect form web for “Haskell中的2个列表的笛卡尔积”

列表理解非常简单。 为了得到列表xsys的笛卡尔乘积,我们只需要对xs每个元素xys每个元素y取元组(x,y)

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

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

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

如果你正在学习Haskell,并希望开发像Monad这样的types类的直觉,那么搞清楚为什么这个稍微短一点的定义是等价的:

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

你可能永远都不会想用真正的代码来写这个,但是基本的想法总是会在Haskell中看到的:我们使用liftM2来将非一元函数(,)提升为一个monad-in这个案例具体是单子列表。

如果这样做没有任何意义或者没有用处,那就把它忘掉 – 这只是看待问题的另一种方式。

如果您的input列表是相同types的,则可以使用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]] 

有一个非常优雅的方式来使用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或(更多理论&#xFF09; http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf细节&#x3002;

正如其他人已经指出的那样,正确的方式是使用列表parsing,但是如果您想要在不使用列表parsing的情况下进行操作,那么您可以这样做:

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

还有一种方法来实现这一点,就是使用应用程序:

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

另一种方法是使用符号:

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

那么,一个很简单的方法就是使用列表parsing:

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

我想我会怎么做,虽然我不是一个Haskell专家(无论如何)。

就像是:

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

其他答案假定两个input列表是有限的。 通常情况下,惯用的Haskell代码包含无限列表,所以在需要的情况下,如何生成无限笛卡儿积是很值得的。

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

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

当然,在任何单行上工作都会给我们无限的元素,然后到达下一行。 同样,按照列的方式将是灾难性的。 但是我们可以沿着对angular线向左下方走,每当我们到达网格的边缘时,再往右开一点。

 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] 

对angular化的低效方法是先沿对angular线再沿对angular线的深度迭代,每次都拉出适当的元素。 为了简单解释,我假设input列表都是无限的,所以我们不必乱搞边界检查。

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

这个实现有点不幸:重复的列表索引操作!! 越来越昂贵,我们走了,给了一个相当不好的渐近performance。 更高效的实现将采取上述想法,但使用拉链实现它。 所以,我们将我们的无限网格分成三种形状:

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

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

 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 ,有(+*+) ,它将上面的cartesian2ddiagonal函数打包在一起,给出了笛卡儿乘积运算:

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

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

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

这里是我的n元笛卡尔积的实现:

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

这是一个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的实现,但是采用一元types。 因此,你可以简化到

 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]] 
  • 列表的所有组合
  • 如何在PHP中生成多个数组中的项目的所有组合
  • 懒洋洋地产生排列
  • algorithm从n返回所有k个元素的组合
  • 显示可能的string组合
  • 字符向量的随机样本,没有元素相互前缀
  • JavaScript - 从m个元素生成n个数组的组合
  • 组合索引如何工作?
  • 用python重复生成排列
  • 在c ++中生成组合
  • 在Javamath组合'NselectR'?