Haskell从列表中删除重复项

我是Haskell的新手，我试着从下面的代码中删除列表中的重复项。但它似乎并不奏效。Haskell从列表中删除重复项

compress []  = [] 
compress (x:xs) = x : (compress $ dropWhile (== x) xs)

我试过了一些搜索，所有的建议都使用foldr/map.head。有基本结构的实现吗？

2015-06-30 Gaara

提示：你有完全正确的想法，除了'dropWhile'是错误的功能。 'dropWhile'删除列表中的每个元素*直到它碰到一个'== x';你需要的东西，而不是像这样删除每个元素。 –

关于这个问题有一个很好的讨论[这里]（http://stackoverflow.com/questions/16108714/haskell-removing-duplicates-from-a-list）。 –

请注意，从'Data.List'模块中有一个内置命名'nub'。 – Sibi

我认为你在代码中提到的问题是你当前的实现只会摆脱相邻的重复。当它发布在评论中时，内置函数nub将消除每个重复，即使它不相邻，也只保留任何元素的第一次出现。但是既然你问过如何用基本的构造来实现这样一个功能，那么这个怎么样呢？

myNub :: (Eq a) => [a] -> [a] 
myNub (x:xs) = x : myNub (filter (/= x) xs) 
myNub [] = []

，我介绍给你有过滤，其过滤基于谓词（名单在这种情况下，该列表中匹配的其余摆脱每一个元素目前唯一的新功能当前元素）。

我希望这会有所帮助。

2015-07-01 01:13:30 fgv

foldr and map是非常基本的FP构建体。然而，它们非常普遍，我发现它们有一段时间了解它的想法。 Tony Morris' talk Explain List Folds to Yourself帮了我很多。

在你的情况下，现有的列表功能像过滤::（一 - >布尔） - > [A] - > [A]与exludes您的重复可以代替dropWhile使用的谓语。

2015-06-30 23:58:41

大多数Haskell实现（当然是GHC）包含的** base **库包含有效设置数据结构，这些数据结构在您添加到它们时执行此操作。结合** Data.Set.fromList **和** Data.Set.toList **可以让你做到这一点，但我不认为图书馆在这里使用你的意图。 –

但是，将列表转换为集合将对元素进行排序并需要Ord约束。 Nub只需要一个Eq约束并保留排序。当然，设置选项在O（n log n）和O（n^2）更有效。在这种情况下，重新排序和/或附加限制可能不是期望的。 – fgv

@fgv你对我的回答有什么看法？我保留Set的建议作为评论，因为它似乎并不符合OP的意图。 –

首先，从来没有简单地陈述“不起作用”的问题。这留给读者检查它是编译时错误，运行时错误还是错误的结果。

在这种情况下，我猜测这是一个错误的结果，这样的：

> compress [1,1,2,2,3,3,1] 
[1,2,3,1]

与您的代码的问题是，它消除连续重复，只。第一对1被压缩，但最后的唯一1并未因此而被删除。

如果可以，请提前对列表进行排序。这将使相同的元素关闭，然后compress做适当的工作。当然，输出的顺序是不同的。如果需要，还可以保留订单（从zip [0..] xs开始，然后进行排序，然后...）。

如果你不能排序因为没有实际的方法来定义比较，但只有一个平等，然后使用nub。请注意，这比分类压缩的效率低得多。这种性能损失是内在的：没有比较器，只能使用低效的二次算法。

2015-07-01 08:27:06 chi

OP的问题是关于实现nub，而不是在库中找到它。对这些问题的讨论很有趣，但没有解决OP或折叠和地图混淆的问题。 –

回答