[Haskell-cafe] Function to detect duplicates
caseyh at istar.ca
Wed Feb 24 17:43:00 EST 2010
On Tue, 23 Feb 2010 08:30:18 -0300, you wrote:
>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.
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, 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
The book "Real World Haskell" has an implementation.
More information about the Haskell-Cafe