[Haskell-cafe] Function to detect duplicates

Ketil Malde ketil at malde.org
Tue Feb 23 07:42:53 EST 2010

Rafael Gustavo da Cunha Pereira Pinto <RafaelGCPP.Linux at gmail.com>

> 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:
> 1) Is there any improvement I can make?

Well - it's a bit long, don't you think?  Long enough that from a
cursory glance, I'd say it's in the "no obvious errors" category.  How
about (inspired by quicksort, as you no doubt can tell):

   noneRepeated [] = True
   noneRepeated (x:xs) = noneRepeated lt && singleton eq && noneRepeated gt
        where lt = filter (<x) xs
              gt = filter (>x) xs
              eq = x:filter (==x) xs
              singleton [_] = True
              singleton _   = False

> 2) Can it be parallelized (par, pseq)?

You could force each of the sublists in parallel, but you might lose
some laziness properties, so I'd carefully benchmark it.

If I haven't seen further, it is by standing in the footprints of giants

More information about the Haskell-Cafe mailing list