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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
