h&&;$      !"#$%&'()*+,-./0123456789:;<=>? Safe-Inferred <@Bryan O'SullivanBSD3%Bryan O'Sullivan unstableportable Safe-Inferred   bloomfilterCompute a 32-bit hash of a value. The salt value perturbs the result. bloomfilterCompute 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. bloomfilterCompute a 32-bit hash. bloomfilterCompute a salted 32-bit hash. bloomfilterCompute a salted 64-bit hash. bloomfilterCompute a list of 32-bit hashes. The value to hash may be inspected as many times as there are hashes requested. bloomfilterCompute a list of 32-bit hashes relatively cheaply. 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 coefficient, we shift right by the coefficient. This offers better performance (as a shift is much cheaper than a multiply), and the low order bits of the final hash stay well mixed.A bloomfilterA fast unchecked shift. Nasty, but otherwise GHC 6.8.2 does a test and branch on every shift.  bloomfilterCompute a 32-bit hash of a B instance.  bloomfilterCompute a 64-bit hash of a B instance.  bloomfilter#Compute a 32-bit hash of a list of B instances.  bloomfilter#Compute a 64-bit hash of a list of B instances. bloomfilter value to hash bloomfiltersalt bloomfilter value to hash bloomfiltersalt bloomfiltersalt bloomfilter value to hash bloomfiltersalt bloomfilter value to hash bloomfilternumber of hashes to compute bloomfilter value to hash bloomfilternumber of hashes to compute bloomfilter value to hash   Bryan O'SullivanBSD3%Bryan O'Sullivan unstableportable Safe-Inferred & bloomfilter+A mutable Bloom filter, for use within the ST monad.( bloomfilterA hash value is 32 bits wide. This limits the maximum size of a filter to about four billion elements, or 512 megabytes of memory.&CDE'F( Safe-Inferred @G bloomfilterA strict pair type.H bloomfilterCompute the nearest power of two greater to or equal than the given number.GIHBryan O'SullivanBSD3%Bryan O'Sullivan unstableportable Safe-InferredL) bloomfilterCreate a new mutable Bloom filter. For efficiency, the number of bits used may be larger than the number requested. It is always rounded up to the nearest higher power of two, but will be clamped at a maximum of 4 gigabits, since hashes are 32 bits in size.J bloomfilterGiven a filter's mask and a hash value, compute an offset into a word array and a bit offset within that word.K bloomfilterHash the given value, returning a list of (word offset, bit offset) pairs, one per hash value.* bloomfilterInsert a value into a mutable Bloom filter. Afterwards, a membership query for the same value is guaranteed to return True.+ bloomfilterQuery 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., bloomfilter3Return the size of a mutable Bloom filter, in bits.L bloomfilterSlow, crummy way of computing the integer log of an integer known to be a power of two.) bloomfilterfamily of hash functions to use bloomfilternumber of bits in filter&'()*+,(&),+*'Bryan O'SullivanBSD3%Bryan O'Sullivan unstableportable Safe-Inferred- bloomfilterAn immutable Bloom filter, suitable for querying from pure code.M bloomfilterCreate an immutable Bloom filter, using the given setup function which executes in the N monad.Example: import Data.BloomFilter.Hash (cheapHashes) filter = create (cheapHashes 3) 1024 $ mf -> do insertMB mf "foo" insertMB mf "bar" 7Note that the result of the setup function is not used./ bloomfilterCreate an immutable Bloom filter from a mutable one. The mutable filter may be modified afterwards.0 bloomfilterCreate an immutable Bloom filter from a mutable one. The mutable filter must not be modified afterwards, or a runtime crash may occur. For a safer creation interface, use / or M.1 bloomfilterCopy an immutable Bloom filter to create a mutable one. There is no non-copying equivalent.2 bloomfilterCreate an empty Bloom filter.(This function is subject to fusion with 5 and 6.3 bloomfilter,Create a Bloom filter with a single element.(This function is subject to fusion with 5 and 6.O bloomfilterGiven a filter's mask and a hash value, compute an offset into a word array and a bit offset within that word.P bloomfilterHash the given value, returning a list of (word offset, bit offset) pairs, one per hash value.4 bloomfilterQuery 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.5 bloomfilterCreate 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.Repeated applications of this function with itself are subject to fusion.6 bloomfilterCreate 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.Repeated applications of this function with itself are subject to fusion.7 bloomfilterQuery 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.8 bloomfilter6Return the size of an immutable Bloom filter, in bits.9 bloomfilterBuild an immutable Bloom filter from a seed value. The seeding function populates the filter as follows.If it returns Q, it is finished producing values to insert into the filter.If it returns R (a,b), a! is added to the filter and b is used as a new seed.: bloomfilterCreate 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 = fromList (cheapHashes 3) 1024 ["foo", "bar", "quux"] M bloomfilterfamily of hash functions to use bloomfilternumber of bits in filter bloomfiltersetup function2 bloomfilterfamily of hash functions to use bloomfilternumber of bits in filter3 bloomfilterfamily of hash functions to use bloomfilternumber of bits in filter bloomfilterelement to insertS bloomfilter'mutation function (result is discarded)9 bloomfilterfamily of hash functions to use bloomfilternumber of bits in filter bloomfilterseeding function bloomfilter initial seed: bloomfilterfamily of hash functions to use bloomfilternumber of bits in filter bloomfiltervalues to populate with&(-./0123456789:(-&/109:2384756.Bryan O'SullivanBSD3%Bryan O'Sullivan unstableportable Safe-Inferred$~= bloomfilterCreate a Bloom filter with the given false positive rate and members. The hash functions used are computed by the  cheapHashes function from the  module.> bloomfilterSuggest 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.The false positive rate is the rate at which queries against the filter should return True when an element is not actually present. It should be a fraction between 0 and 1, so a 1% false positive rate is represented by 0.01.? bloomfilter Behaves as > , but calls T* if given invalid or out-of-range inputs.= bloomfilter!desired false positive rate (0 < e < 1) bloomfiltervalues to populate with> bloomfilterexpected maximum capacity bloomfilter!desired false positive rate (0 < e < 1)? bloomfilterexpected maximum capacity bloomfilter!desired false positive rate (0 < e < 1)-478=>?-=478>?      !"#$%&'()*+,-./01234506789:32;<4=>?@ABCDEFGHIJKLMLNOPQFRSNTFUVFUWXFYZ*bloomfilter-2.0.1.2-ATk8jnBtYF2Ln3Q0Jdm90LData.BloomFilter.HashData.BloomFilter.MutableData.BloomFilterData.BloomFilter.EasyData.BloomFilter.Array!Data.BloomFilter.Mutable.InternalData.BloomFilter.UtilHashHashablehashIO32hashIO64hash32hash64 hashSalt32 hashSalt64hashes cheapHashes hashOne32 hashOne64 hashList32 hashList64 $fHashable[]$fHashable(,,,,)$fHashable(,,,)$fHashable(,,) $fHashable(,)$fHashableEither$fHashableMaybe$fHashableByteString$fHashableByteString0$fHashableWord64$fHashableWord32$fHashableWord16$fHashableWord8$fHashableInt64$fHashableInt32$fHashableInt16$fHashableInt8$fHashableDouble$fHashableFloat $fHashableInt$fHashableChar$fHashableOrdering$fHashableBool$fHashableInteger $fHashable()MBloombitArraynewinsertelemlengthBloomfreeze unsafeFreezethawempty singleton insertListnotElemunfoldfromList $fNFDataBloom $fShowBloomeasyListsafeSuggestSizing suggestSizingnewArraydiv4baseForeign.StorableStorableMBmaskshift:*nextPowerOfTwohashIdxhashesM logPower2createGHC.STSThashesU GHC.MaybeNothingJustmodifyGHC.Errerror