[Haskell-cafe] [ANN] bloomfilter 1.0 - Fast immutable and mutable Bloom filters

[David MacIver]

On Fri, May 30, 2008 at 11:30 PM, Bryan O'Sullivan <bos at serpentine.com> wrote:
> I'm pleased to announce the availability of a fast Bloom filter library
> for Haskell.  A Bloom filter is a probabilistic data structure that
> provides a fast set membership querying capability.  It does not give
> false negatives, but has a tunable false positive rate.  (A false
> positive arises when the filter claims that an element is present, but
> in fact it is not.)
>
> The library is easy to use.  As an example, here's a reimplementation of
> the Unix "spell" command.
>
> import Data.BloomFilter.Easy (easyList, elemB)
>
> main = do
>  filt <- (easyList 0.01 . words) `fmap` readFile "dictionary.txt"
>  let check word | word `elemB` filt = ""
>                 | otherwise         = word ++ "\n"
>  interact (concat . map check . lines)
>
> It is also carefully tuned for performance.  On my laptop, I can sustain
> a construction or query rate well in excess of a million ByteStrings per
> second.
>
> Source code:
>
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bloomfilter
>
> Latest bits:
>
> darcs get http://darcs.serpentine.com/bloomfilter

The Hashable stuff in there looks like it might be independently
useful. Any interest in splitting it out into an independent package
or is it really intended to be something fairly specific to the Bloom
filter implementation?