2016-04-10 47 views
0

Troller, (key,value) çiftleri var. Ben anahtarı veya değeri, listenin sırası değişebilir yinelenen öğeleri kaldırmak gerekir, ancak anahtar veya değerin ilk geçtiği dizilerini listesinde kalmalıdır:Yinelenen anahtarları/değerleri tuple listesinden çıkarma

Örnek:

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

yaptığım ne:

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 

Ama bu çirkin removeDuplicates ("","") something olarak çağrılması gerekir.

+0

denediniz ne nubby ucu için, – epsilonhalbe

+0

hangi hata alıyorsanız – KameeCoding

cevap

3

Sadece uygun karşılaştırıcı ile Data.List paketinden nubBy işlevini kullanabilirsiniz:

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

olarak kullanılır:

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

Ayrıca unutmayın zaman ya ("", "") verimleri yanlış sonuçlarla uygulamanızı çağıran Bir anahtar veya değer ""'dur. Doğru bir ilk argümanı seçmenin tek yolu, girişte görünmeyen bir şey koymaktır, ki bu yapmak biraz can sıkıcıdır. Yukarıdaki uygulama O alır


Not (n^2) Eq örnekleri için en uygun süre,. Bir Ord kısıtlamayı sağlar Eğer bir stabil sıralama algoritması uygular sortBy işlevini kullanın ve bitişik çiftleri kaldırmak için groupBy kullanabilir:

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) 

Bu alır O (nlog n) yerine zaman, ama Açıkça bir Ord kısıtlaması gerektirir.

+0

teşekkür benim çözüm eklemiş ama bence oldukça çirkin @epsilonhalbe sen – KameeCoding

0

Her şeyden önce, bir işlev yazarken bir tür imzası ekleme alışkanlığına girin. Aklı başında ve dürüst olmanızı sağlar, ne yapmak istediğinizi yakalar ve işlevinizi gerçekleştirmeden önce en iyi şekilde yazılır.

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

başka daha genel bir sürümünü sizin dizilerini öğeleri olarak sadece listeleri ile işe yaramaz:

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

İsterseniz

ben böyle bir şey önereceğini, ek parametre olmadan çağrılan etmiş @Bakuriu Eğer

için doğru cevabı vardır -

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

standart fonksiyonları ile sopa istiyorsanız: bu olurdu

0

Akümülatörü bir yardımcı fonksiyona yerleştirin.

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