我正在尝试定义一个从列表中删除重复项的函数。到目前为止，我有一个有效的实现：
rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs) | x `elem` xs = rmdups xs
| otherwise = x : rmdups xs
但是我想在不使用elem. 最好的方法是什么？
我想使用我自己的函数而不是nubor来做到这一点nubBy。
问问题
80570 次
12 回答
60
您的代码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列表元素进行更强的约束，并且还会更改它们在返回列表中的顺序。
于 2013-04-19T16:29:48.190 回答
43
更容易。
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)))
于 2013-09-05T04:35:45.713 回答
26
与@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
基准测试结果
如您所见，基准测试结果证明此解决方案是最有效的。您可以在此处找到此基准测试的来源。
于 2013-04-19T18:17:38.127 回答
22
我认为没有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]) []
于 2013-04-19T16:03:51.373 回答
3
现在回答这个问题为时已晚，但我想分享我的原创解决方案，不使用elem也不假设Ord。
rmdups' :: (Eq a) => [a] -> [a]
rmdups' [] = []
rmdups' [x] = [x]
rmdups' (x:xs) = x : [ k | k <- rmdups'(xs), k /=x ]
该解决方案在输入结束时删除重复项，而问题实现在开始时删除。例如，
rmdups "maximum-minimum"
-- "ax-nium"
rmdups' "maximum-minimum"
-- ""maxiu-n"
此外，此代码复杂度为 O(N*K)，其中 N 是字符串的长度，K 是字符串中唯一字符的数量。N >= K 因此，在最坏的情况下它将是 O(N^2) 但这意味着字符串中没有重复，这与您尝试删除字符串中的重复项不同。
于 2017-09-16T09:12:08.547 回答
2
Graham Huttonrmdups在 p 上有一个函数。86 的Haskell 编程。它保持秩序。如下。
rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs) = x : filter (/= x) (rmdups xs)
rmdups "maximum-minimum"
“maxiu-n”
这一直困扰着我，直到我看到赫顿的功能。然后，我又试了一次。有两个版本，第一个保留最后一个副本，第二个保留第一个。
rmdups ls = [d|(z,d)<- zip [0..] ls, notElem d $ take z ls]
rmdups "maximum-minimum"
“maxiu-n”
如果您想获取列表的第一个而不是最后一个重复元素，就像您尝试做的那样，只需在函数中更改take为drop并将枚举更改zip [0..]为zip [1..].
于 2018-05-05T23:12:18.837 回答
1
我想在@fp_mora 的回答中补充说，在 Haskell 编程的第 136 页上，还有另一个略有不同的实现：
rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x : xs) = x : rmdups (filter (/= x) xs)
我更容易把头绕在这个上面。
于 2021-05-13T18:19:33.840 回答
1
您也可以使用此压缩功能。
cmprs ::Eq a=>[a] -> [a]
--cmprs [] = [] --not necessary
cmprs (a:as)
|length as == 1 = as
|a == (head as) = cmprs as
|otherwise = [a]++cmprs as
于 2019-01-04T06:43:19.397 回答
1
使用递归方案：
import Data.Functor.Foldable
dedup :: (Eq a) => [a] -> [a]
dedup = para pseudoalgebra
where pseudoalgebra Nil = []
pseudoalgebra (Cons x (past, xs)) = if x `elem` past then xs else x:xs
虽然这肯定更先进，但我认为它非常优雅，并展示了一些有价值的函数式编程范例。
于 2017-08-23T03:06:01.477 回答
0
使用 dropWhile 也可以，但请记住在使用它之前对列表进行排序
rmdups :: (Eq a) => [a] -> [a]
rmdups [] = []
rmdups (x:xs) = x : (rmdups $ dropWhile (\y -> y == x) xs)
于 2020-01-09T10:22:13.610 回答
-1
remove_duplicates (x:xs)
| xs == [] = [x]
| x == head (xs) = remove_duplicates xs
| otherwise = x : remove_duplicates xs
你可以尝试这样做。我只是用我自己的实现替换了“elem”。这个对我有用。
于 2020-11-30T18:52:33.430 回答
-1
...或通过使用来自 Data.List 的函数 union 应用于自身：
import Data.List
unique x = union x x
于 2015-11-30T14:56:31.773 回答