从列表中删除成对重复的元素

Question

我熟悉对于包含数字、字符或字符串的列表使用nub函数，但是有人能解释一下如何在一组键值对的列表中使用来自Data.List的nub函数吗？

例如：

[('a', 3),( 'b', 2),('a', 1),('b', 4)]

to

[('a', 3),('b', 2)]

正如您所看到的，我想删除所有键已经存在于列表中的键值对（key, value）。

- sergeantSalty

Answer 1

这是一种方法：

Prelude Data.List> nubBy (\(x,_) (x', _) -> x == x') [('a',1),('b',2),('b',3)]
[('a',1),('b',2)]

- גלעד ברקן

---

@sergeantSalty如果您发现这个答案有用，请接受它以指示未来访问者。 - Haleemur Ali

@Haleemur Ali - sergeantSalty

这个 lambda 也可以写成 (==) `on` fst，其中的 on 是来自于 Data.Function。 - 4castle

所以我已经集成了您的方法来删除重复项，它非常有效。但是我不太理解lambda表达式如何与nubBy函数一起使用。 如果我错了，请纠正我。 nubBy将列表作为参数，并从返回true的相等谓词中删除所有重复项。但是lambda表达式在这里究竟是如何工作的？通过上面给出的示例，有人可以解释一下哪个字符将被用于x和x'吗？ - sergeantSalty

@sergeantSalty，nubBy的lambda类型类似于a -> a -> Boolean。这意味着它是一个具有两个相同类型参数并返回True或False的函数。我选择表示两个元组，形式为(x, _)，表示一个带有x和“任何东西”的元组。在Haskell中，x'或“x prime”只是一种方便的写法 - 我们可以用y代替x'，它只是表示不同的变量。 - גלעד ברקן

Answer 2

您还可以使用“seen”状态变量来跟踪已添加的元素。这类似于“nub”函数，但稍微调整了一下以处理元组列表。它将结果累积到一个“seen”列表中，并检查每个元组的第一个元素是否存在于此列表中。如果在“seen”中找到，则不添加它，否则将其添加到“seen”中。

以下是一个示例：

removeDuplicate :: (Eq a) => [(a, b)] -> [(a, b)]
removeDuplicate lst = go lst []
    where go [] seen = seen
          go (x:xs) seen 
              | any (\(a, _) -> a == fst x) seen = go xs seen
              | otherwise = go xs (seen ++ [x])

它的工作方式如下：

*Main> removeDuplicate [('a', 3),( 'b', 2),('a', 1),('b', 4)]
[('a',3),('b',2)]

这也可以用foldl来写成：

removeDuplicate' = foldl (\seen x -> if any (\(a, _) -> a == fst x) seen
                                     then seen 
                                     else seen ++ [x]) []

最后一种过度的方法是先使用来自 Data.List 的 sortBy 函数按每个元组中第一个元素进行排序，然后使用 groupBy 函数对它们进行分组。然后使用 map() 函数从每个组中取出第一个元组，如下所示：

import Data.List
import Data.Function

removeDuplicate'' :: (Ord a) => [(a, b)] -> [(a, b)]
removeDuplicate'' xs = map head $ groupBy ((==) `on` fst) $ sortBy (compare `on` fst) xs

注意：建议使用 nubBy 的答案是最简单的方法，我只想提供其他实现方式。

此外，第三种方法使用了来自Data.Function的on，使得分组和排序更加容易。

- RoadRunner

Answer 3

与RoadRunner的答案类似，您可以将那个seen实现为一个Set，甚至可以将其包装在State单子中。

module Main where

-- mtl
import Control.Monad.State (State, get, put, evalState)
-- containers
import Data.Set            (Set, empty, insert, member)

removeDuplicates :: Ord a => [(a, b)] -> [(a, b)]
removeDuplicates xs = evalState (go xs) (empty, [])
  where
  go [] = do
    (_, ys) <- get
    return $ reverse ys
  go (x:xs) = do
    (s, ys) <- get
    case member (fst x) s of
      True  -> go xs
      False -> do
        put $ (insert (fst x) s, x:ys)
        go xs

main :: IO ()
main = do
  let testData = [('a', 3),( 'b', 2),('a', 1),('b', 4)]
  print $ removeDuplicates testData

就像RoadRunner的答案一样，再次强调--使用nubBy来完成这个任务。这种方法只适合作为一次练习。

- Adam Smith

Answer 4

我会做以下事情：

λ:> import Data.List (nubBy)
λ:> import Data.Function (on)
λ:> nubBy ((==) `on` snd) [('a',1),('b',2),('b',3)]
[('a',1),('b',2),('b',3)]

- user8174234