[Haskell-cafe] Function to detect duplicates
Rafael Gustavo da Cunha Pereira Pinto
RafaelGCPP.Linux at gmail.com
Tue Feb 23 06:30:18 EST 2010
While solving a puzzle, I was posed the problem of finding if there was no
duplicates on a list.
First I used:
noneRepeated=null.(filter (>1)).(map length).group.sort
But this seemed very unneficient, so I thought that I could detect the
duplicates while sorting, and devised this:
noneRepeated=isNothing . (foldl merge (Just )) . (map sort) . pairs
pairs (x:y:xs)=[x,y]:pairs xs
sort =Just 
sort [x]=Just [x]
sort [x,y] | x>y=Just [y,x]
| y>x=Just [x,y]
merge::(Eq a, Ord a) => Maybe [a]->Maybe [a]->Maybe[a]
merge _ Nothing = Nothing
merge Nothing _ = Nothing
merge (Just ) (Just xs)=Just xs
merge (Just xs) (Just )=Just xs
merge (Just (x:xs)) (Just (y:ys)) | x==y = Nothing
| x>y = (Just y) +? (merge (Just (x:xs))
| x<y = (Just x) +? (merge (Just xs)
(+?) = liftM2 (:)
My version of the merge sort returns Nothing whenever it finds two equal
entries, aborting all subsequent comparisons.
I have a few questions for the friendly people at this cafe:
1) Is there any improvement I can make?
2) Can it be parallelized (par, pseq)?
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe