我的两个列表交集函数存在问题：仅匹配相同位置元素

原inter函数的逻辑是仅当两个列表相同位置的元素相等时才保留，这并不是真正的列表交集（交集要求元素存在于两个列表中即可，与位置无关）。以下是两种常用的正确实现：

1. 多重集交集（保留重复元素） #

这种实现会保留元素的重复次数，比如第一个列表有2个2、第二个列表有3个2时，结果会包含2个2。

inter :: Eq a => [a] -> [a] -> [a]
inter [] _ = []
inter (x:xs) ys
  | x `elem` ys = x : inter xs (removeFirst x ys)
  | otherwise = inter xs ys
  where
    -- 移除列表中第一个出现的指定元素
    removeFirst _ [] = []
    removeFirst y (z:zs)
      | y == z = zs
      | otherwise = z : removeFirst y zs

逻辑说明： #

• 遍历第一个列表的每个元素x，检查它是否存在于第二个列表ys中
• 如果存在，将x加入结果，同时从ys中移除第一个匹配的x（避免同一个x被重复匹配多次）
• 如果不存在，直接跳过该元素，继续处理剩余列表

2. 集合交集（去重） #

如果需要结果中每个元素仅出现一次，可以先对第一个列表去重，再筛选出存在于第二个列表中的元素：

interUnique :: Eq a => [a] -> [a] -> [a]
interUnique xs ys = [x | x <- nub xs, x `elem` ys]
  where
    -- 实现列表去重
    nub [] = []
    nub (x:xs) = x : nub (filter (/= x) xs)

逻辑说明： #

• nub函数用于去除列表中的重复元素
• 通过列表推导式，仅保留去重后列表中存在于ys的元素

原代码问题对比 #

测试inter [1,2,3] [2,1,3]：

• 原函数会返回[3]（仅第三个位置元素相同）
• 修正后的多重集交集会返回[1,2,3]
• 去重交集也会返回[1,2,3]

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