[Haskell-cafe] Re: Function to detect duplicates

[Jonas Almström Duregård]

>>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 <daniel.is.fischer at web.de> wrote:
> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>