éléments uniques dans une liste haskell

Question

Ok, cela va probablement être dans le prélude, mais : existe-t-il une fonction de la bibliothèque standard pour trouver les éléments uniques d'une liste ? ma (ré)implémentation, pour clarification, est la suivante :

has :: (Eq a) => [a] -> a -> Bool
has [] _ = False
has (x:xs) a
  | x == a    = True
  | otherwise = has xs a

unique :: (Eq a) => [a] -> [a]
unique [] = []
unique (x:xs)
  | has xs x  = unique xs
  | otherwise = x : unique xs

Answer 1

J'ai cherché (Eq a) => [a] -> [a] sur Hoogle .

Le premier résultat était nub (supprimer les éléments en double d'une liste).

Hoogle est génial.

Answer 2

El nub de la fonction Data.List (non, ce n'est pas vraiment dans le Prelude) fait quelque chose qui ressemble à ce que vous voulez, mais ce n'est pas tout à fait pareil que votre unique fonction. Ils conservent tous deux l'ordre original des éléments, mais unique conserve la dernière de chaque élément, tandis que nub conserve la première occurrence.

Vous pouvez faire cela pour faire nub agissent exactement comme unique si c'est important (mais j'ai le sentiment que ce n'est pas le cas) :

unique = reverse . nub . reverse

Aussi, nub n'est bon que pour les petites listes. Sa complexité est quadratique, et elle commence à être lente si votre liste peut contenir des centaines d'éléments.

Si vous limitez vos types aux types ayant une instance Ord, vous pouvez améliorer l'échelle. Cette variation sur nub préserve toujours l'ordre des éléments de la liste, mais sa complexité est plus grande. O(n * log n) :

import qualified Data.Set as Set

nubOrd :: Ord a => [a] -> [a] 
nubOrd xs = go Set.empty xs where
  go s (x:xs)
   | x `Set.member` s = go s xs
   | otherwise        = x : go (Set.insert x s) xs
  go _ _              = []

En fait, il a été proposée à ajouter nubOrd a Data.Set .

Answer 3

import Data.Set (toList, fromList)
uniquify lst = toList $ fromList lst

Answer 4

Je pense que unique devrait retourner une liste d'éléments qui n'apparaissent qu'une seule fois dans la liste originale ; c'est-à-dire que tout élément de la liste originale qui apparaît plus d'une fois ne devrait pas être inclus dans le résultat.

Puis-je suggérer une autre définition, unique_alt :

    unique_alt :: [Int] -> [Int]
    unique_alt [] = []
    unique_alt (x:xs)
        | elem x ( unique_alt xs ) = [ y | y <- ( unique_alt xs ), y /= x ]
        | otherwise                = x : ( unique_alt xs )

Voici quelques exemples qui mettent en évidence les différences entre unique_alt et unqiue :

    unique     [1,2,1]          = [2,1]
    unique_alt [1,2,1]          = [2]

    unique     [1,2,1,2]        = [1,2]
    unique_alt [1,2,1,2]        = []

    unique     [4,2,1,3,2,3]    = [4,1,2,3]
    unique_alt [4,2,1,3,2,3]    = [4,1]

Answer 5

Une autre façon de supprimer les doublons :

unique :: [Int] -> [Int]
unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]