Entfernen doppelte Schlüssel/Werte aus Tupel-Liste

Question

Ich habe eine Liste von Tupeln, (key,value) Paare. Ich brauche, um Elemente zu entfernen, die den Schlüssel oder den Wert zu duplizieren, Reihenfolge der Liste kann sich ändern, aber das erste Auftreten des Schlüssels oder der Wert muss in der Liste von Tupeln bleiben:

Beispiel:

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

Was ich gemacht:

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 

Aber dies muss als removeDuplicates ("","") something genannt werden, die hässlich ist.

Answer 1

Sie können einfach verwenden, um die nubBy Funktion aus dem Data.List Paket mit dem entsprechenden Komparator:

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

als:

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

Beachten Sie auch, dass Ihre Implementierung mit ("", "") Ausbeuten falschen Ergebnissen fordern, wenn entweder Ein Schlüssel oder Wert ist "". Die einzige Möglichkeit, ein korrektes erstes Argument zu wählen, besteht darin, etwas zu platzieren, das nicht in der Eingabe erscheint, was etwas nervig ist.

---

beachte, dass die obige Implementierung O (n^2) Zeit in Anspruch nimmt, der für Eq Fälle optimal ist. Wenn Sie eine Ord constraint ermöglichen können, können Sie die sortBy Funktion verwenden, die eine stabile Sortieralgorithmus implementiert, und dann groupBy verwenden, um die zusammenhängenden Duplikate zu entfernen:

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) 

Dies geschieht O (n log n) Zeit statt, aber offensichtlich erfordern eine Ord Einschränkung.

Answer 2

Also vor allem die Angewohnheit, beim Schreiben einer Funktion eine Typensignatur hinzuzufügen. Es hält Sie gesund und ehrlich, es erfasst, was Sie tun möchten, und ist am besten geschrieben, bevor Sie Ihre Funktion implementieren.

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

Wenn Sie wollen, dass es ohne den zusätzlichen Parameter aufgerufen zu haben ist, würde ich so etwas wie dies vorschlagen:

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

Eine weitere allgemeinere Version, die mit Listen als Elemente Ihrer Tupeln nicht nur funktionieren würde, dies wäre:

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' 

Wenn Sie mit Standardfunktionen bleiben wollen - @Bakuriu hat die richtige Antwort für Sie

Answer 3

Setzen Sie den Akku in eine Hilfsfunktion.

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