从Haskell列表中删除重复的元素 [英] Removing repeated elements from a list in Haskell

问题描述

我是Haskell的初学者.我只是想知道如何实现从数组中删除重复元素的功能.例如[1,1,1,3,4,2,2,3]，结果应为[1,3,4,2].我不想使用诸如element之类的现有功能，并通过使用递归来实现此功能.我的想法是比较x:xs，如果x是重复元素，则进行递归，否则重新运行该函数.那是正确的，以及如何通过代码实现呢?

I am a beginner to Haskell. I just wonder how to implement a function to remove the repeat element from an array. for example, [1,1,1,3,4,2,2,3], the result should be [1,3,4,2]. I don't want to use some exist functions like element and implement this by using recursion. My idea is to compare x:xs, if x is a repeat element then do the recursion, else rerun the function. Is that correct and how to implement this by code?

推荐答案

如果您不能假定元素之间的任何顺序(即您不知道它是否是Ord的实例)，则必须使用nub就像已经提到过一个海报.不幸的是，这是O(n ^ 2).

If you cannot assume any ordering between the elements (i.e. you don't know if it's an instance of Ord), then you must use nub like one poster has already mentioned. Unfortunately this is O(n^2).

如果您的元素实现了Ord，则可以对O(nlog(n))中的列表进行排序，然后递归删除相邻的元素(这只会给整个运行时添加O(n)).像这样:

If your elements implement Ord, then you can sort the list in O(nlog(n)) and then remove adjacent elements recursively (which adds just O(n) to the overall runtime). Something like this:

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)

非常有趣的问题.我们经常需要做这种事情. =)

Pretty interesting problem. We often need to do this sort of thing. =)

修改

我没有注意到您给出的结果不是降序排列的.上面的代码将改为生成[1,2,3,4]，这可能不是您想要的.

I didn't notice the result you gave is not in non-decreasing order. The above code will produce [1,2,3,4] instead, which may not be what you want.

这篇关于从Haskell列表中删除重复的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！