list - 从Haskell的列表中删除重复项而不会产生elem

我正在尝试定义一个函数，该函数将从列表中删除重复项。到目前为止，我有一个可行的实现:

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

但是我想在不使用elem的情况下对其进行重做。最好的方法是什么？

我想使用自己的函数而不是nub或nubBy来执行此操作。

最佳答案

我认为如果没有elem(或您自己的重新实现)，您将无法做到。

但是，您的实现存在语义问题。复制元素时，您将保留最后一个。就个人而言，我希望它保留第一个重复项，其余的保留。

*Main> rmdups "abacd"
"bacd"

解决方案是将“可见”元素作为状态变量通过。

removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = rdHelper []
    where rdHelper seen [] = seen
          rdHelper seen (x:xs)
              | x `elem` seen = rdHelper seen xs
              | otherwise = rdHelper (seen ++ [x]) xs

这几乎是在标准库中实现nub的方式(请阅读here源代码)。 nub的实现中的微小差异可确保它是non-strict，而上面的removeDuplicates是严格的(返回之前会消耗整个列表)。

如果您不担心严格性，那么在这里原始递归实际上是多余的。 removeDuplicates可以与foldl一起实现:

removeDuplicates2 = foldl (\seen x -> if x `elem` seen
                                      then seen
                                      else seen ++ [x]) []