Skip to main content
 首页 » 编程设计

list之从没有elem的Haskell列表中删除重复项

2024年10月25日14tuyile006

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

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

但是我想在不使用 elem 的情况下对其进行返工.最好的方法是什么?

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

请您参考如下方法:

您的代码和 nubO(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对列表元素的约束,并且还会更改它们在返回列表中的顺序。