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 _      _  = []

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

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

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