structures-0.2: "Advanced" Data Structures

Safe Haskell	None

Data.Vector.Bloom

Contents

Information
Construction
Modification
Testing
Combining Blooms
Freezing/Thawing

Description

Hierarchical Bloom filters

Synopsis

Documentation

data Bloom Source

Constructors

Bloom !Int !Int !(Vector Word64)

Instances

Eq Bloom
Data Bloom
Ord Bloom
Read Bloom
Show Bloom
Typeable Bloom
Semigroup Bloom

Information

entries :: Bloom -> Int Source

Number of bits set

width :: Bloom -> Int Source

The number of bits in our Bloom filter. Always an integral multiple of 64.

Construction

bloom :: (Foldable f, Hashable a) => Int -> Int -> f a -> Bloom Source

bloom k m builds an m-bit wide Bloom filter that uses k hashes.

Modification

modify :: (forall s. MBloom s -> ST s ()) -> Bloom -> Bloom Source

Given an action on a mutable Bloom filter, modify this one.

insert :: Hashable a => a -> Bloom -> Bloom Source

Insert an element into a Bloom filter.

Testing

elem :: Hashable a => a -> Bloom -> Bool Source

Check if an element is a member of a Bloom filter.

This may return false positives, but never a false negative.

Combining Blooms

union :: Bloom -> Bloom -> Bloom Source

Compute the union of two Bloom filters.

intersection :: Bloom -> Bloom -> Bloom Source

Compute the intersection of two Bloom filters.

Freezing/Thawing

freeze :: PrimMonad m => MBloom (PrimState m) -> m Bloom Source

O(m)

thaw :: PrimMonad m => Bloom -> m (MBloom (PrimState m))Source

O(m)

unsafeFreeze :: PrimMonad m => MBloom (PrimState m) -> m Bloom Source

O(1)

unsafeThaw :: PrimMonad m => Bloom -> m (MBloom (PrimState m))Source

O(1)