Re: [Haskell-cafe] Function to detect duplicates

Hi Rafael, I assume you will perform this operation on some very large lists, or performance would not be an issue. Have you tested if your optimized version is better than your initial one? You should compare your implementation against something like this: import qualified Data.Set as Set noneRepeated :: (Ord a) => [a] -> Bool noneRepeated = accum Set.empty where accum _ [] = True accum s (x:xs) | Set.member x s = False | otherwise = accum (Set.insert x s) xs Also there is some discussion about the nub function that relates to this topic, e.g. http://buffered.io/2008/07/28/a-better-nub/. /Jonas On 23 February 2010 12:30, Rafael Gustavo da Cunha Pereira Pinto wrote:

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

(+?) = 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

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe