Y a-t-il une fonction dans Haskell qui fonctionnerait comme «uniqueBy»?

Nov 21 2020

J'ai besoin d'une fonction qui pourrait être appelée uniqueByqui supprimerait tous les éléments d'une liste de tuples qui ont la même sndvaleur, sans en garder même un comme le nubByferait. Par exemple,

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

devrait revenir [], alors que

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

reviendrait [(1,2)].

Malheureusement, cette fonction uniqueByn'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

2 WillemVanOnsem Nov 21 2020 at 23:12

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)]

nubByprend, 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) .