elementi univoci in un elenco haskell

Question

ok, probabilmente sarà il preludio, ma: esiste una funzione di libreria standard per trovare gli elementi univoci in un elenco? la mia (ri) implementazione, di chiarimenti, è:

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

La funzione nub da Data.List (no, non è in realtà nel Preludio) sicuramente fa qualcosa di simile a quello che vuoi, ma non è proprio la stessa della tua funzione unique. Entrambi mantengono l'ordine originale degli elementi, ma si verifica l'ultima occorrenza di ogni elemento, mentre nub conserva la prima occorrenza.

si può fare questo per fare nub agire esattamente come unique, se questo è importante (anche se ho la sensazione non è):

unique = reverse . nub . reverse 

Inoltre, nub è buono solo per le piccole liste. La sua complessità è quadratica, quindi inizia a rallentare se l'elenco può contenere centinaia di elementi.

Se si limita il tipo ai tipi che hanno un'istanza Ord, è possibile ridimensionarlo meglio. Questa variante nub conserva l'ordine degli elementi della lista, ma la sua complessità è 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 realtà, è stato proposed aggiungere nubOrd a Data.Set.

Answer 2

ho cercato (Eq a) => [a] -> [a] su Hoogle.

Il primo risultato è stato nub (rimuovere gli elementi duplicati da un elenco).

Hoogle è fantastico.

Answer 3

Penso che univoco debba restituire un elenco di elementi che compaiono solo una volta nell'elenco originale; cioè, qualsiasi elemento dell'elenco originale che appare più di una volta non dovrebbe essere incluso nel risultato.

Posso suggerire una definizione alternativa, 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) 

Ecco alcuni esempi che mettono in risalto le differenze tra unique_alt e 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 4

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

Answer 5

Un altro modo per rimuovere i duplicati:

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

Answer 6

Algoritmo in Haskell per creare una lista unica:

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) 

uscita:

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