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]，您可以通过什么方式获取剩余的元素呢？

- user2074245

---

尝试编写一个更简单的案例：crossProdAux :: Int -> [Int] -> [(Int,Int)] - carlosdc

这个最自然的写法是 列表推导式。 - Ingo

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)

- carlosdc

---

我很好奇，你为什么注释掉了你的类型签名？ - Nicolas Wu

可能是因为该函数适用于每种类型，而不仅仅是整数。 - dflemstr

是的...我不想在我的答案中添加不准确的信息（或者更重要的是让提问者感到困惑）。 - carlosdc

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 的前面进行递归处理。

在基本情况下，没有剩余元素需要配对，因此输出为空。

- Nicolas Wu