A hash value is 64 bits wide.

The class of types that can be converted to a hash value.

The instances are meant to be stable, the hash values can be persisted.

An immutable Bloom filter.

Create an immutable Bloom filter, using the given setup function which executes in the ST monad.

Example:

filter = create (sizeForBits 16 2) $ mf -> do
           insert mf "foo"
           insert mf "bar"
 

Note that the result of the setup function is not used.

Build an immutable Bloom filter from a seed value. The seeding function populates the filter as follows.

• If it returns Nothing, it is finished producing values to insert into the filter.
• If it returns Just (a,b), a is added to the filter and b is used as a new seed.

Create a Bloom filter, populating it from a sequence of values.

For example

filt = fromList (policyForBits 10) ["foo", "bar", "quux"]

The version of the format used by serialise and deserialise. The format number will change when there is an incompatible change in the library, such that deserialising and using the filter will not work. This can include more than just changes to the serialised format, for example changes to hash functions or how the hash is mapped to bits.

Note that the format produced does not include this version. Version checking is the responsibility of the user of the library.

The library guarantes that the format version value for the classic (Data.BloomFilter.Classic) and blocked (Data.BloomFilter.Blocked) implementation will not overlap with each other or any previous value used by either implementation. So switching between the two implementations will always be detectable and unambigious.

History:

• Version 1000: original blocked implementation

Serialise the bloom filter to a BloomSize (which is needed to deserialise) and a ByteArray along with the offset and length containing the filter's bit data.

See also formatVersion for compatibility advice.

Parameters for constructing a Bloom filter.

A policy on intended bloom filter size -- independent of the number of elements.

We can decide a policy based on:

1. a target false positive rate (FPR) using policyForFPR
2. a number of bits per entry using policyForBits

A policy can be turned into a BloomSize given a target NumEntries using sizeForPolicy.

Either way we define the policy, we can inspect the result to see:

1. The bits per entry policyBits. This will determine the size of the bloom filter in bits. In general the bits per entry can be fractional. The final bloom filter size in will be rounded to a whole number of bits.
2. The number of hashes policyHashes.
3. The expected FPR for the policy using policyFPR.

Return the size of the Bloom filter.

Query 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.

Query 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.

Same as elem but with the opposite argument order:

x `elem` bfilter

versus

bfilter ? x

A mutable Bloom filter, for use within the ST monad.

Create a new mutable Bloom filter.

The filter size is capped at maxSizeBits.

Insert a value into a mutable Bloom filter. Afterwards, a membership query for the same value is guaranteed to return True.

A bulk insert of many elements.

This is somewhat faster than repeated insertion using insert. It uses memory prefetching to improve the utilisation of memory bandwidth. This has greatest benefit for large filters (that do not fit in L3 cache) and for inserting many elements, e.g. > 10.

To get best performance, you probably want to specialise this function to the Hashable instance and to the lookup action. It is marked INLINABLE to help with this.

Create an immutable Bloom filter from a mutable one. The mutable filter may be modified afterwards.

Copy an immutable Bloom filter to create a mutable one. There is no non-copying equivalent.

Create an immutable Bloom filter from a mutable one without copying. The mutable filter must not be modified afterwards. For a safer creation interface, use freeze or create.

A small family of hashes, for probing bits in a (blocked) bloom filter.

Query an immutable Bloom filter for membership using already constructed Hash value.