einzigartige Elemente in einer Haskell-Liste

Question

okay, das wird wahrscheinlich im Vorspiel sein, aber: gibt es eine Standard-Bibliotheksfunktion zum Finden der einzigartigen Elemente in einer Liste? meine (Wieder-) Einführung, zur Klarstellung, ist:

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

Die nub Funktion von Data.List (nein, es ist eigentlich nicht im Prelude) macht definitiv etwas wie das, was Sie wollen, aber es ist nicht ganz das gleiche wie Ihre unique Funktion. Sie beide die ursprüngliche Reihenfolge der Elemente erhalten, sondern behält den letzten unique Auftreten jedes Elements, während das erste Vorkommen nub beibehält.

können Sie tun dies nub Tat genau wie unique zu machen, wenn das wichtig ist (obwohl ich das Gefühl habe, es ist nicht):

unique = reverse . nub . reverse 

Auch nub für kleine Listen nur gut ist. Seine Komplexität ist quadratisch, so beginnt es langsam zu erhalten, wenn Ihre Liste Hunderte von Elementen enthalten.

Wenn Sie Ihre Typen Typen begrenzen eine Ord Instanz haben, können Sie es besser machen skalieren. Diese Variante nub bewahrt noch die Reihenfolge der Listenelemente, aber seine Komplexität ist 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 _ _    = [] 

In der Tat, es proposednubOrd-Data.Set hinzuzufügen war.

Answer 2

ich für (Eq a) => [a] -> [a] auf Hoogle gesucht.

Erstes Ergebnis war nub (um doppelte Elemente aus einer Liste).

Hoogle ist genial.

Answer 3

Ich denke, dass Unique sollte eine Liste von Elementen, die nur einmal in der ursprünglichen Liste angezeigt werden; Das heißt, alle Elemente der Originalliste, die mehr als einmal angezeigt werden, sollten nicht im Ergebnis enthalten sein.

Darf ich vorschlagen, eine alternative Definition, 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) 

Hier sind einige Beispiele, die die Unterschiede zwischen unique_alt und unqiue markieren:

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 4

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

Answer 5

Ein anderer Weg, um Duplikate zu entfernen:

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

Answer 6

Algorithmus in Haskell eine einzigartige Liste zu erstellen:

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) 

Ausgang:

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