从Haskell中的列表中删除重复项

Question

我正在尝试定义一个将从列表中删除重复项的函数.到目前为止,我有一个有效的实现:

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

但是我想在不使用的情况下重做这件事elem.什么是最好的方法？

我想用我自己的功能而不是nub或者这样做nubBy.

Answer 1

无论你的代码,并nub具有O(N^2)复杂性.

您可以通过排序,分组和仅采用每个组的第一个元素来提高复杂性O(N log N)并避免使用elem.

从概念上讲,

rmdups :: (Ord a) => [a] -> [a]
rmdups = map head . group . sort

假设您从列表开始[1, 2, 1, 3, 2, 4].通过排序,你得到,[1, 1, 2, 2, 3, 4]; 通过分组,你得到,[[1, 1], [2, 2], [3], [4]]; 最后,通过取每个列表的头,你得到[1, 2, 3, 4].

上述的完整实现仅涉及扩展每个功能.

请注意,这需要对Ord列表元素具有更强的约束,并且还会在返回的列表中更改它们的顺序.

Answer 2

更容易.

import Data.Set 
mkUniq :: Ord a => [a] -> [a]
mkUniq = toList . fromList

在O(n)时间内将集合转换为元素列表:

toList :: Set a -> [a]

从O(n log n)时间内的元素列表创建一个集合:

fromList :: Ord a => [a] -> Set a

在python中它也不例外.

def mkUniq(x): 
   return list(set(x)))

Answer 3

与@ scvalex的解决方案相同,以下内容具有O(n * log n)复杂性和Ord依赖性.与之不同的是,它保留了订单,保留了项目的第一次出现.

import qualified Data.Set as Set

rmdups :: Ord a => [a] -> [a]
rmdups = rmdups' Set.empty where
  rmdups' _ [] = []
  rmdups' a (b : c) = if Set.member b a
    then rmdups' a c
    else b : rmdups' (Set.insert b a) c

基准测试结果

如您所见,基准测试结果证明此解决方案是最有效的.您可以在此处找到此基准测试的来源.

Answer 4

我不认为你没有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是在标准库中实现的(在此处阅读源代码).实现中的小差别nub确保它是非严格的,而removeDuplicates上面是严格的(它在返回之前消耗整个列表).

如果你不担心严格,原始递归在这里实际上是过度的.removeDuplicates可以在一行中实现foldl:

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