elementos únicos en una lista de haskell

Question

bien, esto probablemente va a estar en el preludio, pero: ¿hay una función de biblioteca estándar para encontrar los elementos únicos en una lista? mi (re) aplicación, aclaraciones, es:

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 función nub de Data.List (no, en realidad no está en el Preludio) definitivamente hace algo como lo que quiere, pero no es lo mismo que su función unique. Ambos conservan el orden original de los elementos, pero unique conserva la última ocurrencia de cada elemento, mientras que nub conserva la primera aparición.

Usted puede hacer esto para hacer nub actúan exactamente igual que unique, si eso es importante (aunque no tengo la sensación de que no lo es):

unique = reverse . nub . reverse 

Además, nub sólo es bueno para las listas pequeñas. Su complejidad es cuadrática, por lo que comienza a ser lenta si su lista puede contener cientos de elementos.

Si limita sus tipos a tipos que tienen una instancia de Ord, puede hacer que escale mejor. Esta variación en nub aún conserva el orden de los elementos de la lista, pero su complejidad es 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 _ _    = [] 

De hecho, ha sido proposed añadir nubOrd a Data.Set.

Answer 2

Busqué (Eq a) => [a] -> [a] en Hoogle.

Primer resultado fue nub (eliminar elementos duplicados de una lista).

Hoogle es increíble.

Answer 3

Creo que unique debe devolver una lista de elementos que solo aparecen una vez en la lista original; es decir, cualquier elemento de la lista original que aparezca más de una vez no debe incluirse en el resultado.

puedo sugerir una definición 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) 

Éstos son algunos ejemplos que ponen de relieve las diferencias entre unique_alt y 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

Otra manera de eliminar los duplicados:

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

Answer 6

Algoritmo en Haskell para crear una lista única:

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) 

Salida:

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