[Haskell-cafe] Re: Function to detect duplicates

[Ertugrul Soeylemez]

Jonas Almström Duregård <jonas.duregard at gmail.com> wrote:

> >>noneRepeated xs = xs == nub xs
>
> > Not quite as bad, nub is O(n^2)
>
> You are correct of course. Still, it will probably be a bit less
> inefficient if the length of the lists are compared (as opposed to the
> elements):
>
> noneRepeated xs = length xs == length (nub xs)
>
> [...]
>
> > How can you nub in O(n*log n)? Remember, you only have Eq for nub.

Again note that the big advantage of my method is laziness.  The
comparison will end on the first duplicate found.  Using the following
nub implementation the overall time complexity should be O(n * log n),
but may be space-intensive, because it uses O(n) space.  Also note that
it has a different context (the type needs to be Ord instead of Eq):

  import qualified Data.Set as S
  import Data.List

  myNub :: Ord a => [a] -> [a]
  myNub = concat . snd . mapAccumL nubMap S.empty
    where nubMap s x
            | S.member x s = (s, [])
            | otherwise    = (S.insert x s, [x])


Greets
Ertugrul


-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/