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 функцию:

Функция шишка удаляет повторяющиеся элементы из списка. В частности, он сохраняет только первое вхождение каждого элемента. (Название означает «сущность».)

Как и в документации, более общим случаем является 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) 

Answer 2

Если вы хотите определить версию nub для Ord, я рекомендую использовать

nub' :: Ord a => [a] -> [a] 
nub' xs = foldr go (`seq` []) xs empty 
    where 
    go x r obs 
     | x `member` obs = r obs 
     | otherwise = obs' `seq` x : r obs' 
     where obs' = x `insert` obs 

Чтобы посмотреть, что это делает, вы можете избавиться от foldr:

nub' :: Ord a => [a] -> [a] 
nub' xs = nub'' xs empty 
    where 
    nub'' [] obs = obs `seq` [] 
    nub'' (y : ys) obs 
     | y `member` obs = nub'' ys obs 
     | otherwise = obs' `seq` y : nub'' ys obs' 
     where obs' = y `insert` obs 

Один ключевой момент об этой реализации, в отличие от behzad.nouri's, заключается в том, что он производит элементы лениво, поскольку они потребляются. Это, как правило, намного лучше для использования кеша и сбора мусора, а также с использованием постоянного коэффициента меньше памяти, чем алгоритм реверсирования.