Czy w Haskell jest funkcja, która działałaby jak „uniqueBy”?

Question

Potrzebuję funkcji, które można by nazwać uniqueBy, że usunąć wszystkie elementy z listy krotek, które mają taką samą sndwartość, bez zachowania nawet jeden z nich nubBybędzie. Na przykład,

uniqueBy [(1,1),(2,1)]

powinien wrócić [], podczas gdy

uniqueBy [(1,1),(1,1),(1,2)]

wróci [(1,2)].

Niestety ta funkcja uniqueBynie istnieje i nie mogę znaleźć alternatywnej funkcji ani sposobu jej zaimplementowania, chociaż jestem pewien, że musi być łatwy sposób.

Answer 1

Data.ListModuł posiada nubBy :: (a -> a -> Bool) -> [a] -> [a]funkcję. Możesz więc użyć tego w następujący sposób:

import Data.Function(on)
import Data.List(nubBy)

uniqueOnSnd :: Eq b => [(a, b)] -> [(a, b)]
uniqueOnSnd = nubBy ((==) `on` snd)

Na przykład:

Main> uniqueOnSnd  [(4,1), (5,2), (3,1), (2,0)]
[(4,1),(5,2),(2,0)]

nubByzatrzymuje, tak jak nub, O (n = ² ) czasu. Jeśli więc możesz zamówić elementy, lepiej jest najpierw zamówić, a następnie wykonać filtr unikalności, taki jak:

import Data.Function(on)
import Data.List(sortBy)

nubOrderBy :: (a -> a -> Ordering) -> [a] -> [a]
nubOrderBy cmp = go . sortBy cmp
    where go (x1:xs) = x1 : go (dropWhile ((EQ ==) . cmp x1) xs)
          go [] = []

uniqueOnSnd :: Ord b => [(a, b)] -> [(a, b)]
uniqueOrdOnSnd = nubOrderBy (compare `on` snd)

Wadą tego jest to, że nie może działać z nieskończonymi listami, a ponadto kolejność nie zostanie zachowana, ale w ten sposób odfiltrowujemy duplikaty w O (n log n) .