¿Existe una función en Haskell que funcione como 'uniqueBy'?

Question

Necesito una función a la que se pueda llamar uniqueByque elimine todos los elementos de una lista de tuplas que tengan el mismo sndvalor, sin mantener ni siquiera uno de ellos como lo nubByharía. Por ejemplo,

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

debería volver [], mientras que

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

volvería [(1,2)].

Lamentablemente, esta función uniqueByno existe y parece que no puedo encontrar una función alternativa o una forma de implementarla yo mismo, aunque estoy seguro de que tiene que haber una manera fácil.

Answer 1

El Data.Listmódulo tiene una nubBy :: (a -> a -> Bool) -> [a] -> [a]función. Por lo tanto, puede usar esto como:

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

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

Por ejemplo:

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

nubBytoma, al igual que nub, O (n ² ) tiempo. Entonces, en caso de que pueda ordenar los elementos, es más eficiente ordenar primero y luego realizar un filtro único, como:

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)

Una desventaja de esto es que no puede trabajar con listas infinitas y, además, el orden no se conservará, pero aquí filtramos los duplicados en O (n log n) .