如何使用列表删除函数中的重复元素？

Question

对于Haskell来说，我是新手，我对一些事情感到困惑。我正在尝试删除此函数列表中的重复元素：

qsort :: [Int] -> [Int]
qsort [] = []
qsort (x:xs) = 
     qsort smaller ++ [x] ++ qsort larger
     where 
          smaller = [a | a <- xs, a <= x] 
          larger = [b | b <- xs, b > x]

我尝试通过导入Data.List并使用nub []函数来完成此操作：

qsort :: [Int] -> [Int]
qsort [] = nub[]

但是，如果我做qsort [2,6,3,3]，它仍然会以[2,3,3,6]返回。

我使用nub函数错了还是我还缺少其他东西？

谢谢

Answer 1

您的示例显示您只在空列表（nub）上使用nub []，它实际上没有做任何事情。你必须将它应用于qsort主体的结果：

qsort :: [Int] -> [Int]
qsort [] = []
qsort (x:xs) = 
     nub $ qsort smaller ++ [x] ++ qsort larger
     where 
          smaller = [a | a <- xs, a <= x] 
          larger = [b | b <- xs, b > x]

然而，这是不必要的昂贵，因为它在函数的每个分支上运行nub。进一步的优化留给你。

Answer 2

正如@Chad Gilbert's回答中指出的那样，您需要在最终排序列表中应用nub。不幸的是，这个函数是O(n^2)，如果列表变长，它将非常有效。

你可以提高O(nlogn)（排序成本）的总体复杂性，如果你将相同的元素组合在一起，只需要第一个项目，这只是一个O(n)操作。你可以用map，group和head函数完成这个。

有了这些建议，这是编写函数的另一种方法：

import Data.List

qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (pivot:others) = map head $ group $ qsort lowers ++ [pivot] ++ qsort highers
    where lowers = filter (<pivot) others
          highers = filter (>=pivot) others

其工作原理如下：

*Main> qsort [2, 6, 3, 3]
[2,3,6]

Answer 3

请参阅（唯一）[unique包中的https://hackage.haskell.org/package/Unique-0.4.7.2/docs/Data-List-Unique.html]函数。

unique [2,3,6,6,3]
[2,3,6]