[Haskell-cafe] Re: Function to detect duplicates

Ertugrul Soeylemez es at ertes.de
Tue Feb 23 07:59:49 EST 2010

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...

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
algorithm, too, but with the additional laziness advantage.  The article
you linked to contains such an implementation, I think.


nightmare = unsafePerformIO (getWrongWife >>= sex)

More information about the Haskell-Cafe mailing list