为什么 Haskell 中的这个删除重复函数有两个参数而不是一个？

Question

帮助我理解为什么该函数removeDuplicates只有一个参数，但rdHelper它下面的函数有两个？它有效，并且在列表上尝试它没有错误。

removeDuplicates :: Eq a => [a] -> [a] 
removeDuplicates = rdHelper []     
    where rdHelper seen [] = seen  
          rdHelper seen (x:xs)
              | x `elem` seen = rdHelper seen xs 
              | otherwise = rdHelper (seen ++ [x]) xs

也许它与状态变量有关？但我不确定它是什么

Answer 1

为了删除重复项，您需要以某种方式存储您已经看到的值。这就是该变量被称为 的原因seen。最初在递归中，您没有看到任何元素，因此seen是空的。

然而，每次发出一个值时，都会将其添加到 Accumulator 中seen。比如说你打电话removeDuplicates [1,2,3,1,4,2]。然后它将被评估为：

removeDuplicates [1,2,3,1,4,2]
    rdHelper [] [1,2,3,1,4,2]
        (1 : rdHelper [1] [2,3,1,4,2])

所以现在rdHelper将被调用，我们知道1它已经发出，所以我们应该将其过滤掉。接下来我们执行：

removeDuplicates [1,2,3,1,4,2]
    rdHelper [] [1,2,3,1,4,2]
        (1 : rdHelper [1] [2,3,1,4,2])
            (1 : 2 : rdHelper [1,2] [3,1,4,2])
                (1 : 2 : 3 : rdHelper [1,2,3] [1,4,2])

所以现在我们遇到一种情况，其中1is 位于第二个列表的头部，但因为它也是一个elemof seen，所以我们将忽略该元素。

您的代码中有一个错误，因为rdHelper从不发出任何东西。另外请注意，您可以通过添加到头部来提高性能（添加到头部不会改变程序的语义，但会使其运行得更快）：

removeDuplicates :: Eq a => [a] -> [a] 
removeDuplicates = rdHelper []     
    where rdHelper _ [] = []  
          rdHelper seen (x:xs)
              | x `elem` seen = rdHelper seen xs 
              | otherwise = x : rdHelper (x:seen) xs
--                          ^emit element  ^add to head