如何在Haskell中无需引入额外模块实现两个列表的交集运算

原有代码问题梳理 #

• 语法错误：中缀函数调用需要用反引号`包裹，你代码中的'elem'用了单引号，属于语法错误，无法通过编译。
• 变量遮蔽问题：第三个匹配分支中lambda的参数x和模式匹配取出的第一个列表首元素x重名，外层的首元素x被完全遮蔽，没有参与任何判断逻辑。
• 核心逻辑错误：你写的filter (\x -> x 'elem' L2) L2本质是过滤第二个列表中属于第二个列表的元素，返回结果永远是第二个列表本身，完全没有和第一个列表做匹配，也没有对第一个列表剩余的xs做递归处理。

正确实现方案 #

如果你已经提前对两个输入列表做了去重处理，以下两种实现都仅依赖Prelude自带函数，不需要引入额外模块：

高阶函数版本（最简写法） #

intersect :: Eq a => [a] -> [a] -> [a]
intersect l1 l2 = filter (`elem` l2) l1

逻辑说明：遍历第一个列表的所有元素，仅保留同时存在于第二个列表中的元素，返回结果就是两个列表的交集。

递归实现版本 #

intersect :: Eq a => [a] -> [a] -> [a]
intersect [] _ = []
intersect _ [] = []
intersect (x:xs) l2
  | x `elem` l2 = x : intersect xs l2
  | otherwise = intersect xs l2

逻辑说明：递归遍历第一个列表的每个元素，若当前元素存在于第二个列表中则加入结果，否则跳过继续遍历剩余元素。

注意事项 #

• 以上实现的时间复杂度为O(n*m)，适合小规模列表使用，如果处理大规模列表，建议先对两个列表排序，再用双指针法实现，性能会有明显提升。
• 如果你的输入列表没有提前去重，返回结果会保留第一个列表中的重复元素，可以调用你已经实现的去重逻辑对输入或结果做去重处理即可。

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