Existe uma função em Haskell que funcione como 'uniqueBy'?

Question

Eu preciso de uma função que poderia ser chamado de uniqueByque iria remover todos os elementos de uma lista de tuplas que têm o mesmo sndvalor, sem manter até mesmo um deles como nubByfaria. Por exemplo,

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

deve retornar [], enquanto

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

voltaria [(1,2)].

Infelizmente, essa função uniqueBynão existe e não consigo encontrar uma função alternativa ou uma maneira de implementá-la sozinho, embora tenha certeza de que deve haver uma maneira fácil.

Answer 1

O Data.Listmódulo tem uma nubBy :: (a -> a -> Bool) -> [a] -> [a]função. Portanto, você pode usar isso como:

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

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

Por exemplo:

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

nubByleva, assim como nub, tempo O (n ² ) . Portanto, caso você possa ordenar os elementos, é mais eficiente ordenar primeiro e depois executar um filtro de unicidade, 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)

Uma desvantagem disso é que não pode funcionar com listas infinitas e, além disso, a ordem não será preservada, mas aqui filtraremos duplicatas em O (n log n) .