在没有 elem 的情况下从 Haskell 中的列表中删除重复项 [英] 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).

但是，您的实现存在语义问题.当元素被复制时，您将保留最后一个.就我个人而言，我希望它保留第一个重复项并丢弃其余项.

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 在标准库中的实现方式(阅读源代码 此处).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]) []

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