Gibt es in Haskell eine Funktion, die wie 'uniqueBy' funktioniert?

Question

Ich brauche eine Funktion , die aufgerufen werden könnte , uniqueBydas wäre entfernen alle Elemente in einer Liste von Tupeln, die die gleiche haben sndWert, ohne auch nur eine von ihnen als halten nubBywürde. Zum Beispiel,

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

sollte zurückkehren [], während

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

würde zurückkehren [(1,2)].

Leider existiert diese Funktion uniqueBynicht und ich kann anscheinend keine alternative Funktion oder einen Weg finden, sie selbst zu implementieren, obwohl ich sicher bin, dass es einen einfachen Weg geben muss.

Answer 1

Das Data.ListModul hat eine nubBy :: (a -> a -> Bool) -> [a] -> [a]Funktion. Sie können dies also wie folgt verwenden:

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

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

Zum Beispiel:

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

nubBynimmt, so wie nub, O (n ² ) Zeit. Wenn Sie also die Elemente bestellen können, ist es effizienter, zuerst einen Einheitsfilter zu bestellen und dann durchzuführen, wie z.

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)

Ein Nachteil davon ist, dass es nicht mit unendlichen Listen arbeiten kann und außerdem die Reihenfolge nicht beibehalten wird, sondern hier Duplikate in O (n log n) herausfiltert .