在Haskell中从列表中删除重复元素

Question

我是Haskell的初学者。我想知道如何实现从数组中删除重复元素的函数。例如，[1,1,1,3,4,2,2,3]，结果应该是[1,3,4,2]。我不想使用像element这样已经存在的函数，并通过递归来实现。我的想法是比较x:xs，如果x是重复元素，那么就进行递归，否则重新运行函数。这个想法正确吗？如何通过代码实现？

- SPG

---

挑剔：[1,1,1,3,4,2,2,3] 不是一个数组，它是一个链表。性能特征非常不同。 - John L

实际上，这是工作的一部分，我无法解决它。其他部分我已经完成了。 - SPG

Answer 1

如果你不能假设元素之间有任何顺序（即你不知道它是否是 Ord 的一个实例），那么你必须像某个帖子已经提到的那样使用 nub。不幸的是，这是 O(n^2)。

如果你的元素实现了 Ord，那么你可以在 O(nlog(n)) 的时间内对列表进行排序，然后递归地删除相邻的元素（这只会在总运行时间上增加 O(n)）。类似于这样：

remove_dups :: (Ord a, Eq a) => [a] -> [a]
remove_dups xs = remove $ sort xs
  where
    remove []  = []
    remove [x] = [x]
    remove (x1:x2:xs)
      | x1 == x2  = remove (x1:xs)
      | otherwise = x1 : remove (x2:xs)

这是一个相当有趣的问题。我们经常需要做这样的事情。 =)

编辑

我没有注意到你给出的结果不是非递减顺序。上面的代码将产生[1,2,3,4]，这可能不是你想要的。

- Kenji

---

好的，is7s，发帖者并没有说这是他/她的作业。我回答时认为不是作业。 - Kenji

Answer 2

你可以查看Haskell提供的nub函数。 http://www.haskell.org/onlinereport/list.html 这是代码：

nub                     :: (Eq a) => [a] -> [a]
nub                      = nubBy (==)

nubBy                   :: (a -> a -> Bool) -> [a] -> [a]
nubBy eq []              = []
nubBy eq (x:xs)          = x : nubBy eq (filter (y -> not (eq x y)) xs)

实际上，我找到了一个网页，展示了比Haskell提供的更有效的实现方式：http://buffered.io/posts/a-better-nub/

- Yuri

---

@augustss 我在被标记为作业之前就回答了。编辑我找到了有关作业政策的部分（http://meta.stackexchange.com/questions/18242/what-is-the-policy-here-on-homework），尽管它不是官方的，但我会记住它。另一方面，请注意这只是单个谷歌搜索的结果，并且它仅仅是Haskell库提供的实现。换句话说，我没有向他展示任何他自己不能轻松找到的东西。 - Yuri

如果性能很重要，那么也要考虑 nubOrd。 - Thomas M. DuBuisson

Answer 3

你正在正确的轨道上：你正在考虑列表的头部（在你的例子中是x）和尾部（xs）。正如你所建议的，你需要做两件事情：

1. 编写一个函数，从xs中删除任何x的重复项。
2. 处理列表的其余部分...现在xs中任何x的重复项都已经消失了，你该怎么做？在纸上手动尝试一下，并观察你的大脑是如何运作的。

首先尝试解决第一个任务，并确保你编写的函数可以在一些测试用例上工作（在GHCi或其他地方尝试它，直到你满意为止）。

对于第二个任务，再次尝试观察当你手动解决这个问题时，你的大脑是如何运作的，这将有助于你更好地解决问题。

- gspr

Answer 4

这个问题有很多解决方案，最理想的可能取决于你的课程到目前为止所涵盖的内容。

我要指出的是，“存在”函数通常具有对数运行时间，这取决于所使用的数据结构，并且构建最好的数据结构最坏需要“n log n”的时间。

如果这听起来像胡言乱语，请不要担心。您将在算法或复杂性理论课程中学习有关运行时间的知识。我只是说，一个设计良好的“存在”函数比您意识到的要快得多。

顺便说一句，有一种称为哈希函数的东西，可以让您为更大的数组进行更精细的时间空间权衡，但这超出了您当前课程的范围。

- Jeff Burdges

Answer 5

我也在学习Haskell，我写了这段代码。我认为它可以解决你的问题。我尽可能地用最简单的方式来实现。

takeRep :: Eq a => [a] -> [a]  
takeRep [] = []
takeRep (x:xs)
    | checkIt x xs = takeRep xs
    | otherwise = x:takeRep xs

checkIt :: Eq a => a -> [a] -> Bool
checkit _ [] = False
checkIt n (x:xs)
    | n == x = True
    | otherwise = checkIt n xs

- FrancisMars