-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Pure and impure Bloom Filter implementations. -- @package bloomfilter @version 2.0.1.0 -- | A fast, space efficient Bloom filter implementation. A Bloom filter is -- a set-like data structure that provides a probabilistic membership -- test. -- -- -- -- This module provides low-level control. For an easier to use -- interface, see the Data.BloomFilter.Easy module. module Data.BloomFilter.Mutable -- | A hash value is 32 bits wide. This limits the maximum size of a filter -- to about four billion elements, or 512 megabytes of memory. type Hash = Word32 -- | A mutable Bloom filter, for use within the ST monad. data MBloom s a -- | Create 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. new :: (a -> [Hash]) -> Int -> ST s (MBloom s a) -- | Return the size of a mutable Bloom filter, in bits. length :: MBloom s a -> Int -- | 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. elem :: a -> MBloom s a -> ST s Bool -- | Insert a value into a mutable Bloom filter. Afterwards, a membership -- query for the same value is guaranteed to return True. insert :: MBloom s a -> a -> ST s () bitArray :: MBloom s a -> (STUArray s Int Hash) -- | Fast hashing of Haskell values. The hash functions used are Bob -- Jenkins's public domain functions, which combine high performance with -- excellent mixing properties. For more details, see -- http://burtleburtle.net/bob/hash/. -- -- In addition to the usual "one input, one output" hash functions, this -- module provides multi-output hash functions, suitable for use in -- applications that need multiple hashes, such as Bloom filtering. module Data.BloomFilter.Hash class Hashable a where hashIO64 v salt = do { let s1 = fromIntegral (salt `shiftR` 32) .&. maxBound s2 = fromIntegral salt; h1 <- hashIO32 v s1; h2 <- hashIO32 v s2; return $ (fromIntegral h1 `shiftL` 32) .|. fromIntegral h2 } hashIO32 :: Hashable a => a -> Word32 -> IO Word32 hashIO64 :: Hashable a => a -> Word64 -> IO Word64 -- | Compute a 32-bit hash. hash32 :: Hashable a => a -> Word32 hash64 :: Hashable a => a -> Word64 -- | Compute a salted 32-bit hash. hashSalt32 :: Hashable a => Word32 -> a -> Word32 -- | Compute a salted 64-bit hash. hashSalt64 :: Hashable a => Word64 -> a -> Word64 -- | Compute a list of 32-bit hashes. The value to hash may be inspected as -- many times as there are hashes requested. hashes :: Hashable a => Int -> a -> [Word32] -- | Compute 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", -- http://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. cheapHashes :: Hashable a => Int -> a -> [Word32] -- | Compute a 32-bit hash of a Storable instance. hashOne32 :: Storable a => a -> Word32 -> IO Word32 -- | Compute a 64-bit hash of a Storable instance. hashOne64 :: Storable a => a -> Word64 -> IO Word64 -- | Compute a 32-bit hash of a list of Storable instances. hashList32 :: Storable a => [a] -> Word32 -> IO Word32 -- | Compute a 64-bit hash of a list of Storable instances. hashList64 :: Storable a => [a] -> Word64 -> IO Word64 instance Storable a => Hashable [a] instance (Hashable a, Hashable b, Hashable c, Hashable d, Hashable e) => Hashable (a, b, c, d, e) instance (Hashable a, Hashable b, Hashable c, Hashable d) => Hashable (a, b, c, d) instance (Hashable a, Hashable b, Hashable c) => Hashable (a, b, c) instance (Hashable a, Hashable b) => Hashable (a, b) instance (Hashable a, Hashable b) => Hashable (Either a b) instance Hashable a => Hashable (Maybe a) instance Hashable ByteString instance Hashable ByteString instance Hashable Word64 instance Hashable Word32 instance Hashable Word16 instance Hashable Word8 instance Hashable Int64 instance Hashable Int32 instance Hashable Int16 instance Hashable Int8 instance Hashable Double instance Hashable Float instance Hashable Int instance Hashable Char instance Hashable Ordering instance Hashable Bool instance Hashable Integer instance Hashable () -- | A fast, space efficient Bloom filter implementation. A Bloom filter is -- a set-like data structure that provides a probabilistic membership -- test. -- -- -- -- This module provides low-level control. For an easier to use -- interface, see the Data.BloomFilter.Easy module. module Data.BloomFilter -- | A hash value is 32 bits wide. This limits the maximum size of a filter -- to about four billion elements, or 512 megabytes of memory. type Hash = Word32 -- | An immutable Bloom filter, suitable for querying from pure code. data Bloom a -- | A mutable Bloom filter, for use within the ST monad. data MBloom s a -- | Create an immutable Bloom filter from a mutable one. The mutable -- filter may be modified afterwards. freeze :: MBloom s a -> ST s (Bloom a) -- | Copy an immutable Bloom filter to create a mutable one. There is no -- non-copying equivalent. thaw :: Bloom a -> ST s (MBloom s a) -- | Create 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 freeze or -- create. unsafeFreeze :: MBloom s a -> ST s (Bloom a) -- | Build an immutable Bloom filter from a seed value. The seeding -- function populates the filter as follows. -- -- unfold :: (a -> [Hash]) -> Int -> (b -> Maybe (a, b)) -> b -> Bloom a -- | 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 = fromList (cheapHashes 3) 1024 ["foo", "bar", "quux"]
--    
--
fromList :: (a -> [Hash]) -> Int -> [a] -> Bloom a -- | Create an empty Bloom filter. -- -- This function is subject to fusion with insert and -- insertList. empty :: (a -> [Hash]) -> Int -> Bloom a -- | Create a Bloom filter with a single element. -- -- This function is subject to fusion with insert and -- insertList. singleton :: (a -> [Hash]) -> Int -> a -> Bloom a -- | Return the size of an immutable Bloom filter, in bits. length :: Bloom a -> Int -- | 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. elem :: a -> Bloom a -> Bool -- | 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 True will be -- returned. notElem :: a -> Bloom a -> Bool -- | 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. -- -- Repeated applications of this function with itself are subject to -- fusion. insert :: a -> Bloom a -> Bloom a -- | 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. -- -- Repeated applications of this function with itself are subject to -- fusion. insertList :: [a] -> Bloom a -> Bloom a bitArray :: Bloom a -> (UArray Int Hash) instance NFData (Bloom a) instance Show (Bloom a) -- | An easy-to-use Bloom filter interface. module Data.BloomFilter.Easy -- | An immutable Bloom filter, suitable for querying from pure code. data Bloom a -- | Create a Bloom filter with the given false positive rate and members. -- The hash functions used are computed by the cheapHashes -- function from the Hash module. easyList :: Hashable a => Double -> [a] -> Bloom a -- | 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. elem :: a -> Bloom a -> Bool -- | 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 True will be -- returned. notElem :: a -> Bloom a -> Bool -- | Return the size of an immutable Bloom filter, in bits. length :: Bloom a -> Int -- | 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. -- -- 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. safeSuggestSizing :: Int -> Double -> Either String (Int, Int) -- | Behaves as safeSuggestSizing, but calls error if given -- invalid or out-of-range inputs. suggestSizing :: Int -> Double -> (Int, Int)