Re: [Haskell-cafe] Re: Function to detect duplicates

...

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) On 23 February 2010 14:09, Daniel Fischer wrote:

Am Dienstag 23 Februar 2010 13:59:49 schrieb Ertugrul Soeylemez:

...

Jonas Almström Duregård 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

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe