Haskell中两个列表的笛卡尔积

Question

Haskell中两个列表的笛卡尔积

83

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

15个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Redu · Answer 1

这是一个关于序列的任务。它的单子实现可能如下所示：

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

- Manoj R · Answer 2

对于热爱者来说，还有一种方法，只需使用递归模式匹配即可。

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

- Christian Oudard · Answer 3

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

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

- enigmaticPhysicist · Answer 4

如果你只想要笛卡尔积，以上任何答案都可以。通常，笛卡尔积是达到某个目的的手段。通常，这意味着将元组的元素绑定到一些变量，x和y，然后在它们上面调用一些函数f x y。如果这本来就是计划，那么你最好完全使用单子：

do
    x <- [1, 2]
    y <- [6, 8, 10]
    pure $ f x y

这将生成列表[f 1 6，f 1 8，f 1 10，f 2 6，f 2 8，f 2 10]。

- Darshan D · Answer 5

递归模式匹配，不使用列表推导式

crossProduct [] b=[]
crossProduct (x : xs) b= [(x,b)] ++ crossProduct xs b

cartProd _ []=[]
cartProd x (u:uv) = crossProduct x u ++ cartProd x uv