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)] 这不是一个真正的家庭作业问题，并不涉及任何这样的问题，但解决这个问题的方式可能有助于一个我坚持。
列表理解非常简单。 为了得到列表xs和ys的笛卡尔乘积，我们只需要对xs每个元素x和ys每个元素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或（更多理论）; http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf细节。;
正如其他人已经指出的那样，正确的方式是使用列表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 ，有(+*+) ，它将上面的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)]
如果该结构变得有用，您也可以看到对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]]
