Удаление повторяющихся ключей/значений из списка tuple

Question

У меня есть список кортежей, (key,value) пар. Мне нужно, чтобы удалить элементы, которые дублируют ключ или значение, порядок списка можно изменить, но первое вхождение ключа или значения должны оставаться в списке кортежей:

Пример:

input: [("r","w"),("n","j"),("a","j"),("d","i"),("s","g"),("r","a")] 
output: [("r","w"),("n","j"),("d","i"),("s","g")] 

Что я сделал:

removeDuplicates _ [] = [] 
removeDuplicates seen (x:xs) 
         | elem (head $ fst x) (fst seen) = [] ++ removeDuplicates seen xs 
         | elem (head $ snd x) (snd seen) = [] ++ removeDuplicates seen xs 
         | otherwise = x:removeDuplicates ((fst seen)++(fst x),(snd seen)++(snd x)) xs 

Но это должно называться removeDuplicates ("","") something, которая некрасиво.

Answer 1

Вы можете просто использовать функцию nubBy из Data.List пакета с соответствующим компаратором:

removeDuplicates xs = nubBy cmpKeyAndVal xs 
    where 
    cmpKeyAndVal (x, y) (x', y') = x == x' || y == y' 

Используется как:

> removeDuplicates [("r","w"),("n","j"),("a","j"),("d","i"),("s","g"),("r","a")] 
[("r","w"),("n","j"),("d","i"),("s","g")] 

Также обратите внимание, что вызов вашей реализации с ("", "") Урожайность неверных результатов, когда либо ключ или значение "". Единственный способ выбрать правильный первый аргумент - поставить что-то, что не появляется на входе, что немного раздражает.

---

Обратите внимание, что выше реализация занимает O (N^2) время, которое является оптимальным для Eq экземпляров. Если вы можете позволить Ord ограничения вы можете использовать функцию sortBy, которая реализует алгоритм стабильная сортировки, а затем использовать groupBy для удаления смежных дубликатов:

import Data.List(sortBy, groupBy) 
import Data.Ord(comparing) 
import Data.Function(on) 

removeDuplicates xs = sortAndGroupBy snd (sortAndGroupBy fst xs) 
    where 
    sortAndGroupBy f = map head . groupBy ((==) `on` f). sortBy (comparing f) 

Это занимает O (Nlog п) вместо этого, но очевидно, требуется ограничение Ord.

Answer 2

Так что, прежде всего, привыкните добавлять подпись типа при написании функции. Он держит вас в здравом уме и честен, он захватывает то, что вы хотите сделать, и лучше всего писать, прежде чем выполнять свою функцию.

removeDuplicates :: (Eq a, Eq a1) => ([a], [a1]) -> [([a], [a1])] -> [([a], [a1])] 

Если вы хотите, чтобы он вызывается без дополнительного параметра, я хотел бы предложить что-то вроде этого:

remove :: (Eq a, Eq a1) => [([a], [a1])] -> [([a], [a1])] 
remove = removeDuplicates ("","") 

Еще более общий вариант, который не будет работать только со списками как элементы ваших кортежей , было бы это:

removeX :: (Eq t, Eq s) => [(t, s)] -> [(t, s)] 
removeX [] = [] 
removeX (xx@(x,y):xs) = let xs' = filter (\(a,b) -> not (a == x || b ==y)) xs 
         in xx:removeX xs' 

Если вы хотите придерживаться стандартных функций - @Bakuriu имеет правильный ответ для вас

Answer 3

Поместите аккумулятор в вспомогательную функцию.

removeDuplicates lst = rd lst [] 
         where rd _ [] = [] 
          rd seen (x:xs) = ...