如何用Haskell实现笛卡尔积函数cprod？zip/map使用遇阻求指导

嘿，我懂你想要实现的这个cprod函数——本质上是一种笛卡尔积，但顺序是先把第二个列表的每个元素和第一个列表的所有元素配对，对吧？你提到用zip不行，这很正常，因为zip只是把两个列表对应位置的元素配对，完全不是我们要的全组合；至于map，其实可以通过嵌套或者结合concatMap来实现，我给你拆解一下思路：

方法一：用列表推导式（最直观） #

Haskell的列表推导式天生适合这种生成元素组合的场景，你只需要控制遍历的顺序就能得到想要的结果：

cprod :: [a] -> [b] -> [(a, b)]
cprod xs ys = [(x, y) | y <- ys, x <- xs]

解释一下：我们先遍历第二个列表ys的每个元素y，然后对每个y，再遍历第一个列表xs的每个元素x，把它们配对成(x,y)。这样就会先生成所有x和第一个y的配对，再处理下一个y，完全符合你要的输出效果。

测试一下：

cprod [1,2,3] ['a','b']
-- 输出 [(1,'a'),(2,'a'),(3,'a'),(1,'b'),(2,'b'),(3,'b')]

方法二：用concatMap结合map（对应你提到的map思路） #

如果你想用map来实现，可以把问题拆成两步：

1. 对ys里的每个y，生成一个包含(x,y)的列表（x来自xs）
2. 把这些小列表拼接成一个大列表

用concatMap就能一步完成这两个操作，代码如下：

cprod :: [a] -> [b] -> [(a, b)]
cprod xs ys = concatMap (\y -> map (\x -> (x, y)) xs) ys

内层的map (\x -> (x,y)) xs会把xs里的每个元素转换成和当前y配对的元组，比如当y='a'时，这一步会得到[(1,'a'),(2,'a'),(3,'a')]；然后concatMap会把ys中每个y对应的这个列表全部拼接起来，最终得到目标结果。

为什么zip不行？ #

顺便说下你提到的zip的问题：zip的逻辑是按位置配对，它只会取两个列表中较短的那个长度，把第n个元素和第n个元素配对，比如zip [1,2,3] ['a','b']只会得到[(1,'a'),(2,'b')]，既没有覆盖所有组合，顺序也不对，所以完全不适合这个需求。

如果你想了解标准库的相关函数，Data.List里的sequence可以生成笛卡尔积，但它的顺序是先遍历第一个列表的元素，再遍历第二个，比如sequence [[1,2,3], ['a','b']]会得到[(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]，和你要的顺序相反，所以还是我们上面的两种方法更直接。

内容的提问来源于stack exchange，提问作者John