unique des éléments dans une liste haskell

bon d'accord, c'est probablement va être dans le prélude, mais: est-il une norme fonction de la bibliothèque pour trouver les éléments dans une liste? ma (re)mise en œuvre, pour la clarification, est:

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
  • Votre has est également de série, c'est juste flip elem.
  • Ou même has xs = (`elem` xs).
  • pourquoi êtes-vous à l'aide de elem comme infixe?
  • Parce que elem a type Eq a => a -> [a] -> Bool afin de l'utiliser comme un infixe la section de fonctionnement fait xs le deuxième argument. (`elem` xs) est délactosé à (\x -> elem x xs) qui est ce que nous voulons ici!
InformationsquelleAutor muhmuhten | 2010-06-23
  1. 50

    La nub fonction de Data.List (non, ce n'est pas vraiment dans le Prélude) n'a décidément quelque chose comme ce que vous voulez, mais il n'est pas tout à fait le même que celui de votre unique fonction. Ils ont à la fois de préserver l'ordre original des éléments, mais unique conserve le dernier
    l'apparition de chaque élément, tandis que nub conserve la première occurrence.

    Vous pouvez faire pour vous nub agissent exactement comme les unique, si c'est important (même si j'ai un sentiment qu'il n'est pas):

    unique = reverse . nub . reverse

    Aussi, nub est seulement bon pour les petites listes.
    Sa complexité est quadratique, donc ça commence à devenir lent si votre liste peut contenir plusieurs centaines d'éléments.

    Si vous limitez vos types de types ayant un Ord exemple, vous pouvez le faire à l'échelle de mieux.
    Cette variation sur nub conserve l'ordre des éléments de la liste, mais sa complexité est 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é pour ajouter nubOrd à Data.Set.

    • Sans doute de son mieux pour laisser tout simplement comme un ensemble plutôt que d'utiliser une liste, en premier lieu,
    • Soyons honnêtes: nub n'est pas bon pour tout liste de. Même sur la liste avec les 2 éléments nubOrd est rapide.
    • C'est comme une sorte de "carte tamis" semblable à l'impur "de hachage tamis".
    • Il y avait une faute de frappe dans un type de fonction de signature. Devrait être Ord a. Aussi, j'ai trouvé que nubOrd curieusement (ou pas) n'est pas vraiment mieux que la bosse dans mon cas. Il a été encore plus lente. Probablement parce qu'il n'y avait pas beaucoup de valeurs en double (bien que l'introduction de nub couper l'exécution de moitié le temps, nub ord était d'environ 20% plus lent que juste nub).
    • les fonctions sur les listes peuvent être plus utiles que l'équivalent sur les jeux de maintien de l'ordre des éléments. Cela peut être très important.
    InformationsquelleAutor Yitz
  2. 93

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

    Premier résultat a été partie (supprimer les doublons d'éléments à partir d'une liste).

    Hoogle est génial.

    • Aussi, vous pouvez vous offrir propres à l'égalité de la fonction comme ceci : nubBy :: (a -> a -> Bool) -> [a] -> [a]
    • Et si Bart est temps que nous pourrions voir un nubOrd, qui sera plus raisonnable performance sage.
    • Il convient de dire que la nub fonction est de Data.List paquet.
    • Les données.Liste.Unique a sortUniq, qui est le "nubOrd" que vous demandez. Je préfère avoir un (Eq a, Hashable a) => [a] -> [un] qui serait encore plus raisonnable, en terme de performance...
    • Jusqu'à présent, j'ai été vraiment du mal à comprendre comment utiliser efficacement les Hoogle, n'a jamais songé à la recherche pour le type de signature, je suis à la recherche d'
    InformationsquelleAutor Artelius
  3. 10
    import Data.Set (toList, fromList)
uniquify lst = toList $ fromList lst
    • Cela modifie l'ordre des éléments.
    InformationsquelleAutor Daniel Patru
  4. 4

    Je pense que unique doit renvoyer une liste d'éléments qui n'apparaissent qu'une fois dans la liste d'origine, qui est, à tous les éléments de l'original de la liste qui apparaissent plus d'une fois ne devraient pas être inclus dans le résultat.

    Puis-je suggérer une définition alternative, 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]
    • C'est en fait la définition de Données.Liste.Unique (unique) bien que personnellement, je n'ai jamais couru à ce cas d'utilisation, tandis que le "squash listes pour ne contenir qu'un seul des doublons" la fonction est du pain et du beurre dans de nombreuses opérations.
    InformationsquelleAutor Adam Grant
  5. 2

    Je pense que ce serait-il le faire.

    unique [] = []
unique (x:xs) = x:unique (filter ((/=) x) xs)
    InformationsquelleAutor Craig Norton
  6. 0

    Une autre façon de supprimer les doublons:

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

    Algorithme en Haskell pour créer une liste unique:

    data Foo = Foo { id_ :: Int
               , name_ :: String
               } deriving (Show)

alldata = [ Foo 1 "Name"
          , Foo 2 "Name"
          , Foo 3 "Karl"
          , Foo 4 "Karl"
          , Foo 5 "Karl"
          , Foo 7 "Tim"
          , Foo 8 "Tim"
          , Foo 9 "Gaby"
          , Foo 9 "Name"
          ]

isolate :: [Foo] -> [Foo]
isolate [] = []
isolate (x:xs) = (fst f) : isolate (snd f)
  where
    f = foldl helper (x,[]) xs
    helper (a,b) y = if name_ x == name_ y
                     then if id_ x >= id_ y
                          then (x,b)
                          else (y,b)
                     else (a,y:b)

main :: IO ()
main = mapM_ (putStrLn . show) (isolate alldata)

    De sortie:

    Foo {id_ = 9, name_ = "Name"}
Foo {id_ = 9, name_ = "Gaby"}
Foo {id_ = 5, name_ = "Karl"}
Foo {id_ = 8, name_ = "Tim"}
    InformationsquelleAutor Manuel