multiplos - elementos únicos en una lista de haskell

multiplicar haskell

Question

bien, esto probablemente estará en el preludio, pero ¿hay una función de biblioteca estándar para encontrar los elementos únicos en una lista? mi (re) implementación, para aclarar, 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

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

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

Hoogle es increíble.

Answer 2

Creo que eso único debería 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 )

Aquí hay algunos ejemplos que resaltan 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 3

La función nub de Data.List (no, en realidad no está en el Preludio) definitivamente hace algo como lo que quieres, pero no es lo mismo que tu función unique . Ambos conservan el orden original de los elementos, pero el unique conserva la última ocurrencia de cada elemento, mientras que nub retiene la primera ocurrencia.

Puedes hacer esto para que nub actúe exactamente como unique , si eso es importante (aunque tengo la sensación de que no lo es):

unique = reverse . nub . reverse

Además, nub solo es bueno para 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 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, se ha proposed agregar nubOrd a Data.Set .

Answer 4

Otra forma de eliminar duplicados:

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

Answer 5

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"}

Answer 6

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