从Haskell的列表中删除重复项而没有elem [英] Removing duplicates from a list in Haskell without elem

问题描述

我正在尝试定义一个函数，该函数将从列表中删除重复项.到目前为止，我有一个可行的实现方案:

I'm trying to define a function which will remove duplicates from a list. So far I have a working implementation:

rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs)   | x `elem` xs   = rmdups xs
                | otherwise     = x : rmdups xs

但是，我想在不使用elem的情况下对其进行重做.最好的方法是什么?

However I'd like to rework this without using elem. What would be the best method for this?

我想使用自己的功能而不是nub或nubBy.

I'd like to do this using my own function and not nub or nubBy.

推荐答案

我认为没有elem(或者您自己重新实现)，您将无法做到.

I don't think you'll be able to do it without elem (or your own re-implementation of it).

但是，您的实现存在语义问题.复制元素时，您将保持 last 的位置.就我个人而言，我希望它保留第一个重复项，其余的保留下来.

However, there is a semantic issue with your implementation. When elements are duplicated you're keeping the last one. Personally, I'd expect it to keep the first duplicate item and drop the rest.

*Main> rmdups "abacd"
"bacd"

解决方案是将可见"元素作为状态变量通过.

The solution is to thread the 'seen' elements through as a state variable.

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

这几乎是在标准库中实现nub的方式(请阅读源代码非严格，而上面的removeDuplicates是严格(返回之前会消耗掉整个列表).

This is more-or-less how nub is implemented in the standard library (read the source here). The small difference in nub's implementation ensures that it is non-strict, while removeDuplicates above is strict (it consumes the entire list before returning).

如果您不担心严格性，那么在这里进行原始递归实际上是过大的选择. removeDuplicates可以与foldl一起在一行中实现:

Primitive recursion is actually overkill here, if you're not worried about strictness. removeDuplicates can be implemented in one line with foldl:

removeDuplicates2 = foldl (\seen x -> if x `elem` seen
                                      then seen
                                      else seen ++ [x]) []

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