问列表列表的交集Haskell

EN

当您注意到一个形式为a -> a -> a的函数时，您可能正在处理一个可以与monoid一起使用的函数，这意味着您可以使用folds。

在您的例子中，intersection []实际上没有一个合理的输出，所以应该使用一个需要非空输入列表的折叠函数，比如foldr1。

因此，一种简单的实现方式是：

intersection:: (Eq a) => [[a]] -> [a]
intersection = foldr1 intersect

两个集合的交集是关联的(也是可交换的，但在这里不是那么重要)。即：

intersect(A, B, C) = intersect(intersect(A,B), C) = intersect(A, intersect(B, C))

这意味着无论你以什么顺序进行交集操作，结果都不会改变。

因此，在Haskell中，您可以利用foldl1函数对所有列表应用intersect函数：

> import Data.List
> foldl1 intersect [[1,5,3,11],[1,5,2,11],[5,3,2,11]]
[5,11]

简易方法专业技巧：

专业技巧：

两个列表的交集是显而易见的。

3个列表的交集是第三个列表与前2个列表的交集。

所以你要做的就是记住你当前的交集结果，并将它与下一个列表相交，直到你用完所有的列表，或者直到你的交集为空。

在复杂性方面，更好的方法是使用类似合并排序的方法。

当你的威胁列表就像列表的元素，而不是理解的时候，在元素上使用intersect并返回它们的交集。

合并操作也将是一个交集。

我已经很久没有和Haskell打交道了，所以不幸的是，我不能给你提供代码样本。