タプルリストから重複したキー/値を削除する

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

あなただけの適切なコンパレータでData.ListパッケージからnubBy機能を使用することができます。

として使用

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")] 

はまた、いずれかの場合に("", "")で実装を呼び出すと、誤った結果が得られていることに注意してくださいキーまたは値は""です。最初の正しい引数を選択する唯一の方法は、入力に表示されないものを配置することです。これは少し面倒です。上記の実装はEqインスタンスに最適なO（N^2）の時間を要すること

---

注。あなたは安定ソートアルゴリズムを実装しsortBy機能を使用して、連続的な重複を削除するgroupByを使用することができますOrd制約を許可することができた場合：

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 n）で時間がかかりますが、明らかに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) = ...