Is there a function in Haskell that would work like 'uniqueBy'?

user_12632540 0
Viewed 148

I need a function that could be called uniqueBy that would remove all elements in a list of tuples that have the same snd value, without keeping even one of them as nubBy would. For example,

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

should return [], whereas

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

would return [(1,2)].

Sadly this function uniqueBy does not exist and I can't seem to find an alternative function or a way to implement it myself, although I'm sure there has to be an easy way.

unique list haskell
1 Answers

The Data.List module has a nubBy :: (a -> a -> Bool) -> [a] -> [a] function. You thus can use this like:

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

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

For example:

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

nubBy takes, just like nub, O(n2) time. So in case you can order the elements, it is more efficient to first order and then perform a uniqness filter, like:

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)

A disadvantage of this is that it can not work with infinite lists, and furthermore that the order will not be preserved, but here w thus filter out duplicates in O(n log n).

user_675790
Related