是否有一个函数接受一个列表和 returns 该列表中重复元素的列表？

Question

是否有一个 Haskell 函数接受一个列表和 returns 该列表中 duplicates/redundant 个元素的列表？

我知道 nub 和 nubBy 函数，但它们 删除了 重复项；我想保留这些骗子并将它们收集在一个列表中。

Answer 1

Is there a Haskell function that takes a list and returns a list of duplicates/redundant elements in that list?

你自己写一个这样的函数就够轻松的了。使用一个带有两个列表参数的辅助函数，第一个是要查找其欺骗对象的列表；沿着那个列表走，并在第二个参数中积累欺骗；最后，return 后者，当第一个参数是空列表时。

dupes l                                    = dupes' l []
  where
    dupes' []     ls                       = ls
    dupes' (x:xs) ls
        | not (x `elem` ls) && x `elem` xs = dupes' xs (x:ls)
        | otherwise                        = dupes' xs ls

测试：

λ> dupes [1,2,3,3,2,2,3,4]
[3,2]

请注意，渐近时间复杂度与 nub 一样糟糕，不过：O(n^2)。如果你想要更好的渐近，你需要一个 Ord class 约束。

Answer 2

如果您对 Ord 约束感到满意，您可以使用 Data.List 中的 group:

getDups :: Ord a => [a] -> [a]
getDups = concatMap (drop 1) . group . sort

Answer 3

执行此操作的最简单方法（效率极低）是使用 nub 和 \:

import Data.List (nub, (\))

getDups :: Eq a => [a] -> [a]
getDups xs = xs \ nub xs

如果你能忍受 Ord 约束，一切都会变得更好：

import Data.Set (member, empty, insert)

getDups :: Ord a => [a] -> [a]
getDups xs = foldr go (const []) xs empty
  where
    go x cont seen
      | member x seen = x : r seen
      | otherwise = r (insert x seen)

Answer 4

我写了这些函数，看起来运行良好。

第一个return列表中的重复元素列表，具有基本的相等性测试(==)

duplicate :: Eq a => [a] -> [a]
duplicate  []             =  []
duplicate  (x:xs)         
    | null pres = duplicate  abs
    | otherwise = x:pres++duplicate  abs
  where (pres,abs) = partition (x ==) xs

第二个通过提供等式测试功能来完成同样的工作（如nubBy）

duplicateBy :: (a -> a -> Bool) -> [a] -> [a]
duplicateBy eq []             =  []
duplicateBy eq (x:xs)         
    | null pres = duplicateBy eq abs
    | otherwise = x:pres++duplicateBy eq abs
  where (pres,abs) = partition (eq x) xs

是否有一个函数接受一个列表和 returns 该列表中重复元素的列表？

Is there a function that takes a list and returns a list of duplicate elements in that list?

haskell

functional-programming

list