我正在尝试定义一个从列表中删除重复项的函数。到目前为止,我有一个有效的实现:
rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs) | x `elem` xs = rmdups xs
| otherwise = x : rmdups xs
但是我想在不使用
elem
的情况下对其进行返工.最好的方法是什么?
我想使用我自己的函数而不是
nub
来执行此操作或
nubBy
.
请您参考如下方法:
您的代码和 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
对列表元素的约束,并且还会更改它们在返回列表中的顺序。