Unique items on the haskell list

Question

In order, this will probably be a prelude, but: is there a standard library function for finding unique items in a list? my (re) implementation, for clarification, is this:

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

The nub function from Data.List (no, it's not actually in Prelude) definitely does something like what you want, but it's not exactly the same as your unique function. They preserve the original order of elements, but unique preserves the last occurrence of each element, and nub preserves the first occurrence.

You can do this to make nub act just like unique if that is important (although I don't have that feeling):

 unique = reverse . nub . reverse 

In addition, nub is only suitable for small lists. Its complexity is quadratic, so it starts to slow down if your list can contain hundreds of items.

If you restrict your types to types that have an Ord instance, you can improve its scaling. This option on nub still preserves the order of the list items, but its complexity is 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 xs) xs go _ _ = [] 

In fact, suggested adding nubOrd to Data.Set .

Answer 2

I searched (Eq a) => [a] -> [a] on Hoogle .

The first result was nub (remove duplicate items from the list).

Hoogle is awesome.

Answer 3

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

Answer 4

I think that unique should return a list of elements that appear only once in the original list; that is, any elements of the source list that appear more than once should not be included in the result.

You can suggest an 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 ) 

Here are a few examples that highlight the differences between unique_alt and 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 5

Haskell's algorithm for creating a unique list:

 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) 

Output:

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

Answer 6

Another way to remove duplicates:

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