úÎ U^S+     =This is a workaround for poor optimisation in GHC 6.8.2. It C fails to notice constant-width shifts, and adds a test and branch < to every shift. This imposes about a 10% performance hit. A strict pair type. >Compute the nearest power of two greater to or equal than the  given number.  !  !!portableunstable%Bryan O'Sullivan <bos@serpentine.com> ;Compute a single hash of a value. The salt value perturbs  the result. >Compute two hashes of a value. The first salt value perturbs ? the first element of the result, and the second salt perturbs  the second. Compute a hash. ACompute a list of hashes. The value to hash may be inspected as + many times as there are hashes requested. -Compute a list of hashes relatively cheaply. A The value to hash is inspected at most twice, regardless of the  number of hashes requested. +We use a variant of Kirsch and Mitzenmacher's technique from "Less : Hashing, Same Performance: Building a Better Bloom Filter",   7http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf. <Where Kirsch and Mitzenmacher multiply the second hash by a E coefficient, we shift right by the coefficient. This offers better C performance (as a shift is much cheaper than a multiply), and the 3 low order bits of the final hash stay well mixed. "?A fast unchecked shift. Nasty, but otherwise GHC 6.8.2 does a ! test and branch on every shift. Compute a hash of a # instance. Compute two hashes of a # instance. Compute a hash of a list of # instances.  Compute two hashes of a list of # instances.    portableunstable%Bryan O'Sullivan <bos@serpentine.com> AAn immutable Bloom filter, suitable for querying from pure code. +A mutable Bloom filter, for use within the $ monad. AA hash value is 32 bits wide. This limits the maximum size of a D filter to about four billion elements, or 512 megabytes of memory. BCreate a new mutable Bloom filter. For efficiency, the number of B bits used may be larger than the number requested. It is always 0 rounded up to the nearest higher power of two. $For a safer creation interface, use . To convert a A mutable filter to an immutable filter for use in pure code, use  . ACreate an immutable Bloom filter, using the given setup function  which executes in the $ monad.  Example:   import Data.BloomFilter.Hash (cheapHashes)  (filter = createB (cheapHashes 3) 1024 $ mf -> do  insertMB mf "foo"  insertMB mf "bar" 8Note that the result of the setup function is not used. %Given a filter'0s mask and a hash value, compute an offset into 1 a word array and a bit offset within that word. &<Hash the given value, returning a list of (word offset, bit $ offset) pairs, one per hash value. '<Hash the given value, returning a list of (word offset, bit $ offset) pairs, one per hash value. ;Insert a value into a mutable Bloom filter. Afterwards, a = membership query for the same value is guaranteed to return True. >Query a mutable Bloom filter for membership. If the value is  present, return True). If the value is not present, there is  still some possibility that True will be returned. AQuery an immutable Bloom filter for membership. If the value is  present, return True). If the value is not present, there is  still some possibility that True will be returned. BCreate an immutable Bloom filter from a mutable one. The mutable  filter must not0 be modified afterwards, or a runtime crash may - occur. For a safer creation interface, use . BCopy an immutable Bloom filter to create a mutable one. There is  no non-copying equivalent. 4Return the size of a mutable Bloom filter, in bits. 7Return the size of an immutable Bloom filter, in bits. @Build an immutable Bloom filter from a seed value. The seeding + function populates the filter as follows.  If it returns (%, it is finished producing values to  insert into the filter.  If it returns ) (a,b), a is added to the filter and  b is used as a new seed. ?Create an immutable Bloom filter, populating it from a list of  values. !Here is an example that uses the  cheapHashes function from the  Data.BloomFilter.Hash' module to create a hash function that  returns three hashes.  import Data.BloomFilter.Hash (cheapHashes)  'filt = fromListB (cheapHashes 3) 1024 ["foo", "bar", "quux"] *BSlow, crummy way of computing the integer log of an integer known  to be a power of two.       portableunstable%Bryan O'Sullivan <bos@serpentine.com>=Create a Bloom filter with the given false positive rate and 7 members. The hash functions used are computed by the  cheapHashes  function from the Data.BloomFilter.Hash module. =Suggest a good combination of filter size and number of hash = functions for a Bloom filter, based on its expected maximum - capacity and a desired false positive rate. AThe false positive rate is the rate at which queries against the  filter should return True! when an element is not actually B present. It should be a fraction between 0 and 1, so a 1% false ' positive rate is represented by 0.01.   +      !"#$%&'()&*+,-./01234bloomfilter-1.0Data.BloomFilter.HashData.BloomFilterData.BloomFilter.EasyData.BloomFilter.UtilbaseForeign.StorableControl.Monad.ST Data.MaybeHashablehashIOhashIO2hashhashes cheapHasheshashOnehashTwohashList hashList2Bloom bitArrayBMBloom bitArrayMBHashnewMBcreateBinsertMBelemMBelemBunsafeFreezeMBthawMBlengthMBlengthBunfoldB fromListBeasyList suggestSizing FastShift:*nextPowerOfTwoshiftLshiftRdiv4StorableGHC.STSThashIdxhashesMhashesUNothingJust logPower2