[Haskell-cafe] Re: Function to detect duplicates
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