如何在 Haskell 中找到两个列表的交集？

Question

我在 Haskell 中使用两个列表作为“集合”，我应该找到并返回两个列表的交集。我有措施从列表中删除重复项，但是我无法想到如何实际比较列表并获取另一个仅包含两个列表中都存在的元素的列表。这是我到目前为止所拥有的

intersect :: [Integer] -> [Integer] -> [Integer]
intersect [] _ = []
intersect _ [] = []
intersect (x:xs) L2 = filter (\x -> x 'elem' L2) L2

然而，这是不正确的，但从逻辑上讲，我无法确切地想到如何使这项工作发挥作用。任何想法和建议将不胜感激！另外，如果有人有任何不涉及导入任何其他模块的想法会更好，因为我只想依赖前奏中的函数。

Answer 1

您应该使用 backtics 将函数用作中缀运算符，因此x `elem` L2. 此外，您在这里使用了L2两次（并且由于L2以大写字母开头，编译器会认为这L2是一个数据构造函数）。您应该使用另一个列表中的项目来过滤一个列表。Integer是一种类型，因此以大写字符开头。

如果我们这样解决上述问题，我们得到：

intersect :: [Integer] -> [Integer] -> [Integer]
intersect [] _ = []
intersect _ [] = []
intersect xs ys = filter (\x -> x `elem` xs) ys

或更短：

intersect :: [Integer] -> [Integer] -> [Integer]
intersect [] = const []
intersect xs = filter (`elem` xs)

然而，如果是一个无限列表并且其中至少有一项最终没有为列表生成，则这些将不起作用。可以使用对角化来最终生成两个列表中出现的所有项目。可以使用该包来实现此目的。xsysxscontrol-monad-omega