[Haskell-cafe] Function to detect duplicates

Casey Hawthorne caseyh at istar.ca
Wed Feb 24 17:43:00 EST 2010

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,

If space is at a premium you might want to look at a 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.

More information about the Haskell-Cafe mailing list