Haskell:从列表中删除重复的元组？

Question

我试图从前到后获得状态.是否有方便的Haskell函数从列表中删除重复的元组？或者它可能有点复杂,比如遍历整个列表？

Before: the list of tuples, sorted by word, as in
   [(2,"a"), (1,"a"), (1,"b"), (1,"b"), (1,"c"), (2,"dd")]
After: the list of sorted tuples with exact duplicates removed, as in
   [(2,"a"), (1,"a"), (1,"b"), (1,"c"), (2,"dd")]

Answer 1

Eq a => [a] -> [a]在hoogle上搜索,返回nub功能:

nub函数从列表中删除重复的元素.特别是,它只保留每个元素的第一次出现.(名称nub的意思是"本质".)

在文档中,更一般的情况是nubBy.

也就是说,这是一种O(n^2)算法,可能效率不高.Data.Set.fromList如果值是Ord类类的实例,则可以使用另一种方法,如:

import qualified Data.Set as Set

nub' :: Ord a => [a] -> [a]
nub' = Set.toList . Set.fromList

虽然这不会保持原始列表的顺序.

维护原始列表顺序的简单设置样式解决方案可以是:

import Data.Set (Set, member, insert, empty)

nub' :: Ord a => [a] -> [a]
nub' = reverse . fst . foldl loop ([], empty)
    where
    loop :: Ord a => ([a], Set a) -> a -> ([a], Set a)
    loop acc@(xs, obs) x
        | x `member` obs = acc
        | otherwise = (x:xs, x `insert` obs)