haskell - Haskell笛卡尔积递归

Question

我知道如何使用列表推导来做到这一点，但是如何实现一个函数，该函数将递归计算给定两组的笛卡尔积？

这就是我被困的地方（而且我是菜鸟）

crossProd :: [Int] -> [Int] -> [(Int,Int)]
crossProd xs ys | xs == [] || ys == [] = []
                | otherwise = (head xs, head ys) : crossProd (tail xs) (ys)

这个输出给了我

[(1,4),(1,5),(1,6)]

如果集合是[1,2,3]和[4,5,6]分别.. 我将如何获得其余部分？

Answer 1

最基本的情况是这样的：

{-crossProdAux :: Int -> [Int] -> [(Int,Int)]-}
crossProdAux x []    = []
crossProdAux x (a:b) = (x, a):(crossProdAux x b)

{-crossProd :: [Int] -> [Int] -> [(Int,Int)]-}
crossProd [] ys   = []
crossProd (a:b) ys= (crossProdAux a ys)++(crossProd b ys)

Answer 2

这可以在一个函数中完成：

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

请注意，我已经概括了您的类型，因此这适用于任何aand b，而不仅仅是Ints。

此函数的关键是了解您希望将第一个列表中的每个元素与第二个列表中的每个元素配对。因此，此解决方案从第一个列表中获取一个元素x，并将其与ys. 这是通过映射一个函数来完成的，该函数y从中获取每个值ys，并将其转换为一对(x, y)。我们将它添加到与列表的其余部分一起递归的前面xs。

在基本情况下，没有任何东西可以配对，因此输出为空。