Y a-t-il une fonction dans Haskell qui fonctionnerait comme «uniqueBy»?
J'ai besoin d'une fonction qui pourrait être appelée uniqueBy
qui supprimerait tous les éléments d'une liste de tuples qui ont la même snd
valeur, sans en garder même un comme le nubBy
ferait. Par exemple,
uniqueBy [(1,1),(2,1)]
devrait revenir []
, alors que
uniqueBy [(1,1),(1,1),(1,2)]
reviendrait [(1,2)]
.
Malheureusement, cette fonction uniqueBy
n'existe pas et je n'arrive pas à trouver une fonction alternative ou un moyen de l'implémenter moi-même, même si je suis sûr qu'il doit y avoir un moyen facile.
Réponses
Le Data.Listmodule a une nubBy :: (a -> a -> Bool) -> [a] -> [a]fonction. Vous pouvez donc utiliser ceci comme:
import Data.Function(on)
import Data.List(nubBy)
uniqueOnSnd :: Eq b => [(a, b)] -> [(a, b)]
uniqueOnSnd = nubBy ((==) `on` snd)
Par exemple:
Main> uniqueOnSnd [(4,1), (5,2), (3,1), (2,0)]
[(4,1),(5,2),(2,0)]
nubBy
prend, tout comme nub
, O (n 2 ) temps. Donc, dans le cas où vous pouvez ordonner les éléments, il est plus efficace de le premier ordre, puis d' effectuer un filtre d'unité, comme:
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)
Un inconvénient de ceci est qu'il ne peut pas fonctionner avec des listes infinies, et de plus que l'ordre ne sera pas préservé, mais ici nous filtrons donc les doublons dans O (n log n) .