úÎzlv &      !"#$%&=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>,-./01234;Compute a 32-bit hash of a value. The salt value perturbs  the result. value to hash salt 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. value to hash salt Compute a 32-bit hash. Compute a salted 32-bit hash. salt value to hash Compute a salted 64-bit hash. salt value to hash ;Compute a list of 32-bit hashes. The value to hash may be 8 inspected as many times as there are hashes requested. number of hashes to compute value to hash 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. number of hashes to compute value to hash 5?A fast unchecked shift. Nasty, but otherwise GHC 6.8.2 does a ! test and branch on every shift. 6789: 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. ABCD+A mutable Bloom filter, for use within the E monad. FGHIAA 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 A rounded up to the nearest higher power of two, but clamped at a : maximum of 4 gigabits, since hashes are 32 bits in size. $For a safer creation interface, use . To convert a A mutable filter to an immutable filter for use in pure code, use  .  family of hash functions to use number of bits in filter JKLACreate an immutable Bloom filter, using the given setup function  which executes in the E 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.  family of hash functions to use number of bits in filter %setup function (result is discarded) Create an empty Bloom filter. (This function is subject to fusion with   and .  family of hash functions to use number of bits in filter -Create a Bloom filter with a single element. (This function is subject to fusion with   and .  family of hash functions to use number of bits in filter element to insert MGiven a filter'0s mask and a hash value, compute an offset into 1 a word array and a bit offset within that word. N<Hash the given value, returning a list of (word offset, bit $ offset) pairs, one per hash value. O<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. (mutation function (result is discarded) ?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 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 P%, it is finished producing values to  insert into the filter.  If it returns Q (a,b), a is added to the filter and  b is used as a new seed.  family of hash functions to use number of bits in filter seeding function  initial 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"]  family of hash functions to use number of bits in filter values to populate with RBSlow, 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. desired false positive rate (0 < e < 1) values to populate with $=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. expected maximum capacity desired false positive rate (0 < e < 1) % Behaves as $ , but calls S if given ! invalid or out-of-range inputs. expected maximum capacity desired false positive rate (0 < e < 1)   #$% # $%#$%T      !"#$%&'()*+,-.//0123456789:;<=>?@ABCDEFGHIJK@LMNOPQRSTUVW@XY@XZ[@\]^bloomfilter-1.2.6.4Data.BloomFilter.HashData.BloomFilterData.BloomFilter.EasyData.BloomFilter.UtilData.BloomFilter.ArrayHashablehashIO32hashIO64hash32hash64 hashSalt32 hashSalt64hashes cheapHashes hashOne32 hashOne64 hashList32 hashList64Bloom bitArrayBMBloom bitArrayMBHashnewMBcreateBemptyB singletonBinsertMBelemMBelemBmodifyBinsertB insertListBnotElemBunsafeFreezeMBthawMBlengthMBlengthBunfoldB fromListBeasyListsafeSuggestSizing suggestSizing FastShiftshiftLshiftR:*nextPowerOfTwoc_endc_stepc_fragc_begin hashLittle2 hashLittle hashWord2hashWord HashStatediv4 alignedHashwith alignedHash2 doubleHashrechunkbaseForeign.StorableStorableunsafeUseAsCStringLenunsafeAdjustCStringLen hashChunksmemsetnewArrayBhashBshiftBmaskBGHC.STSTMBhashMBshiftMBmaskMBmaxHash logBitsInHashlogBytesInHashhashIdxhashesMhashesU Data.MaybeNothingJust logPower2GHC.Errerror