[Haskell-cafe] Function to detect duplicates

[Casey Hawthorne]

On Tue, 23 Feb 2010 08:30:18 -0300, you wrote:

>Hi folks,
>
>While solving a puzzle, I was posed the problem of finding if there was no
>duplicates on a list.

Must it be a list data structure(DS) or list ADT?

Mergesort can be parallelized.

>
>Best regards,
>
>Rafael


If space is at a premium you might want to look at a Bloom Filter.

http://en.wikipedia.org/wiki/Bloom_filter

The Bloom filter, conceived by Burton Howard Bloom in 1970,[1] is a
space-efficient probabilistic data structure that is used to test
whether an element is a member of a set. False positives are possible,
but false negatives are not. Elements can be added to the set, but not
removed (though this can be addressed with a counting filter). The
more elements that are added to the set, the larger the probability of
false positives.


The book "Real World Haskell" has an implementation.
--
Regards,
Casey