Haskell：从列表中删除重复项

Question

我是Haskell的新手，我正在尝试以下代码从列表中删除重复项。但它似乎不起作用。

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

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

- Gaara

---

提示：您的想法完全正确，只是dropWhile函数不正确。dropWhile会删除列表中每个元素，直到遇到一个等于x的元素；您需要删除所有像那样的元素。 - Tikhon Jelvis

这个主题在这里有一个很好的讨论。 - Chris R. Timmons

请注意，Data.List 模块中有一个内置的名为 nub 的函数可以实现此功能。 - Sibi

@TikhonJelvis 你确定吗？ GHCi 给出的结果是 dropWhile (==1) [1,1,1,2,3,1,4,5,6] ==> [2,3,1,4,5,6]。 - chi

@TikhonJelvis chi 是对的。你的意思是 "直到它不等于 x"。 - jub0bs

哦，是的，完全搞反了，抱歉！无论如何，“dropWhile”都不是正确的函数。 - Tikhon Jelvis

Answer 1

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

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

我在这里向您介绍的唯一新功能是filter，它可以根据谓词（在本例中，为了摆脱与当前元素匹配的列表其余元素）过滤列表。

希望这有所帮助。

- fgv

Answer 2

首先，在问题中不要简单地陈述“不起作用”。这会让读者检查它是编译时错误、运行时错误还是错误的输出结果。

在这种情况下，我猜测它是错误的输出结果，就像这样:

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

你的代码问题在于它只删除连续的重复项。第一对“1”被压缩了，但是最后一个单独的“1”没有被删除。

如果可以的话，请提前对列表进行排序。这将使相等的元素靠近，然后“压缩”做正确的工作。输出结果当然会是不同的顺序。如果需要保持顺序，也有办法（从“zip [0..] xs”开始，然后排序，然后...）。

如果不能排序，因为实际上没有办法定义比较，但只有相等性，则使用“nub”。请注意，这比排序和压缩要低得多。这种性能损失是固有的：没有比较器，您只能使用低效的二次算法。

- chi

---

OP的问题是关于实现nub，而不是在库中找到它。讨论问题很有趣，但并没有解决这个问题，也没有解决OP对折叠和映射的困惑。 - Alain O'Dea

Answer 3

foldr和map是非常基本的FP构造。然而，它们非常通用，我很长一段时间都觉得它们有点令人费解。Tony Morris的演讲“向自己解释列表折叠”对我帮助很大。

在您的情况下，可以使用具有排除重复项谓词的现有列表函数，例如filter :: (a -> Bool) -> [a] -> [a]代替dropWhile。

- Alain O'Dea

---

大多数 Haskell 实现（当然包括 GHC）都包含了高效的 Set 数据结构，可以在添加元素时完成此操作。结合 Data.Set.fromList 和 Data.Set.toList 可以实现这一点，但我认为库并不符合你的意图。 - Alain O'Dea

然而，将列表转换为集合将对元素进行排序并需要Ord约束。Nub仅需要Eq约束并保留排序。当然，集合选项在O（n log n）vs O（n ^ 2）方面更有效率。重新排序和/或附加约束在这种情况下可能不可取。 - fgv

@fgv，你认为我的答案怎么样？我将“Set”建议作为评论保留，因为它似乎并不符合原帖的意图。 - Alain O'Dea

我认为您的回答将引导原帖作者朝着正确的方向前进。从性能的角度来看，使用set或map的想法也很好，只是它会重新排序元素并增加额外的约束条件，这可能不是原帖作者想要的... - fgv

我完全同意。我对发布基于库使用的Data.Set.fromList的评论感到犹豫，但您对输出顺序以及输入上的Ord约束的识别，更重要的考虑因素是它们改变了OP函数的类型。 - Alain O'Dea