[Haskell-cafe] Re: Function to detect duplicates

[Daniel Fischer]

Am Dienstag 23 Februar 2010 13:59:49 schrieb Ertugrul Soeylemez:
> Jonas Almström Duregård <jonas.duregard at gmail.com> wrote:
> > Ertugrul: while your solution is minimalistic, Rafael deemed his
> > ~n*log n implementation too inefficient. Thus your ~n^3 implementation
> > is hardly an improvement...

Not quite as bad, nub is O(n^2).

>
> My variant has an advantage, though.  It is completely lazy, so it will
> take a shortcut, as soon as a duplicate is found.  Depending on his
> application, this may be useful or not.
>
> I think the nub-based solution is the best one in general, but it's the
> base library implementation of nub, which is unfortunate.  In fact, with
> a better nub implementation, this becomes an O(n * log n) time

How can you nub in O(n*log n)? Remember, you only have Eq for nub.

> algorithm, too, but with the additional laziness advantage.  The article
> you linked to contains such an implementation, I think.
>
>
> Greets
> Ertugrul