Hi folks,
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:
import Control.Monad
import Data.Maybe
noneRepeated=isNothing . (foldl merge (Just [])) . (map sort) . pairs
pairs []=[]
pairs [x]=[[x]]
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]
| x==y=Nothing
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))
(Just ys))
| x<y = (Just x) +? (merge (Just xs)
(Just (y:ys)))
(+?) = 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)?
Best regards,
Rafael
