从 Haskell 列表中删除重复元素

我是 Haskell 的初学者。我只是想知道如何实现一个函数来从数组中删除重复元素。例如，[1,1,1,3,4,2,2,3]，结果应为[1,3,4,2]。我不想使用一些现有的函数（例如 element）并通过使用递归来实现它。我的想法是比较 x:xs，如果 x 是重复元素则进行递归，否则重新运行该函数。这是正确的以及如何通过代码实现它？

如果您无法假设元素之间的任何顺序（即您不知道它是否是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)

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

Edit

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