úÎ f»d%      !"#$%=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 32-bit hash of a value. The salt value perturbs  the result. 8Compute a 64-bit hash of a value. The first salt value ? perturbs the first element of the result, and the second salt  perturbs the second. Compute a 32-bit hash. Compute a salted 32-bit hash. Compute a salted 64-bit hash. ;Compute a list of 32-bit hashes. The value to hash may be 8 inspected as many times as there are hashes requested. BCompute a list of 32-bit hashes relatively cheaply. The value to E 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 32-bit hash of a - instance. Compute a 64-bit hash of a - instance. #Compute a 32-bit hash of a list of - instances. #Compute a 64-bit hash 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. Create an empty Bloom filter. (This function is subject to fusion with   and . -Create a Bloom filter with a single element. (This function is subject to fusion with   and . /Given a filter'0s mask and a hash value, compute an offset into 1 a word array and a bit offset within that word. 0<Hash the given value, returning a list of (word offset, bit $ offset) pairs, one per hash value. 1<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. ?Create a new Bloom filter from an existing one, with the given  member added. =This function may be expensive, as it is likely to cause the $ underlying bit array to be copied. BRepeated applications of this function with itself are subject to  fusion. ?Create a new Bloom filter from an existing one, with the given  members added. =This function may be expensive, as it is likely to cause the $ underlying bit array to be copied. BRepeated applications of this function with itself are subject to  fusion. BQuery an immutable Bloom filter for non-membership. If the value  is present, return False&. If the value is not present, there  is still some possibility that False 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 2 %, it is finished producing values to  insert into the filter.  If it returns 3  (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"] 4BSlow, 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.   #$ # $#$5     !"#$%&'()*+,-./01230456789:; < =>?bloomfilter-1.2.2Data.BloomFilter.HashData.BloomFilterData.BloomFilter.EasyData.BloomFilter.UtilData.BloomFilter.ArraybaseForeign.StorableControl.Monad.ST Data.MaybeHashablehashIO32hashIO64hash32hash64 hashSalt32 hashSalt64hashes cheapHashes hashOne32 hashOne64 hashList32 hashList64Bloom bitArrayBMBloom bitArrayMBHashnewMBcreateBemptyB singletonBinsertMBelemMBelemBmodifyBinsertB insertListBnotElemBunsafeFreezeMBthawMBlengthMBlengthBunfoldB fromListBeasyList suggestSizing FastShift:*nextPowerOfTwoshiftLshiftRnewArraydiv4StorableGHC.STSThashIdxhashesMhashesUNothingJust logPower2