Bloom Filter in Haskell

Question

I recently implemented a Bloom Filter in Haskell and, although I am not new to functional programming, I am a beginner when it comes to Haskell itself.

I'll gladly take any feedback regarding the implementation or the code style. I tried to stick to the Haskell conventions regarding function and variable naming, but I may have gotten some stuff wrong.

You will notice that I'm using my own implementation of a Bitset, you can assume it behaves like a normal one (I sure hope so).

module DataStructures.BloomFilter (empty, insert, member, DataStructures.BloomFilter.null) where
import System.Random (random, StdGen)
import qualified DataStructures.Bitset as Bitset
import Data.Hashable (hashWithSalt)
-- n: expected number of items in the Bloom Filter
-- p: acceptable probability of a false positive
-- m: max number of bits the Bloom Filter will use
-- k: number of hashing functions
data BloomFilter = BloomFilter {
 n :: Int, p :: Float, bitset :: Bitset.Bitset, m :: Int, k :: Int, hashSeed :: Int
} deriving (Eq, Show)
getMaxSize :: Int -> Float -> Int
getMaxSize n p = abs $ ceiling $ fromIntegral n * (log p) / (log (1 / (log 2 ^ 2)))
getNumberOfHashFunctions :: Int -> Int -> Int
getNumberOfHashFunctions n m = round $ fromIntegral (m `div` n) * log 2
empty :: Int -> Float -> StdGen -> BloomFilter
empty n p randGen =
 let m = getMaxSize n p
 k = getNumberOfHashFunctions n m
 hashSeed = fst $ random randGen
 in BloomFilter n p Bitset.empty m k hashSeed
null :: BloomFilter -> Bool
null = Bitset.null . bitset
getHashes :: Show a => BloomFilter -> a -> [Int]
getHashes bloomFilter elem =
 let str = show elem
 seed = hashSeed bloomFilter
 maxSize = m bloomFilter
 in (`mod` maxSize) . abs . (`hashWithSalt` str) . (seed +) <$> [1..(k bloomFilter)]
insert :: Show a => BloomFilter -> a -> BloomFilter
insert bloomFilter elem =
 let hashes = getHashes bloomFilter elem
 newBitset = Bitset.insertMany (bitset bloomFilter) hashes
 in bloomFilter { bitset = newBitset }
-- Returns whether an element *may be* present in the bloom filter.
-- This function can yield false positives, but not false negatives.
member :: Show a => BloomFilter -> a -> Bool
member bloomFilter elem =
 let hashes = getHashes bloomFilter elem
 bs = bitset bloomFilter
 in all (Bitset.member bs) hashes

I would have liked to use a murmur3 hashing function but all Haskell implementations use types that I'm not yet familiar with (Word32, ByteString).

Answer 1

Instead of transforming everything to String using Show just for the purpose of hashing it, you should constraint element types to be Hashable instead:

getHashes :: Hashable a => BloomFilter -> a -> [Int]
getHashes bloomFilter elem =
 let seed = hashSeed bloomFilter
 maxSize = m bloomFilter
 in (`mod` maxSize) . abs . (`hashWithSalt` elem) . (seed +) <$> [1..(k bloomFilter)]

I'd also use maxSize and numFuns as the field names in BloomFilter and then use RecordWildCards:

getHashes :: Hashable a => BloomFilter -> a -> [Int]
getHashes BloomFilter{..} elem = map nthHash [1..numFuns]
 where
 nthHash n = abs (hashWithSalt (n + hashSeed) elem) `mod` maxSize 

Or maybe even nicer:

getHashes :: Hashable a => BloomFilter -> a -> [Int]
getHashes BloomFilter{..} elem = 
 [ abs (hashWithSalt (i + hashSeed) elem) `mod` maxSize | i <- [1..numFuns] ]

• Bertrand: Oh I did not know about the RecordWildCards thing. Very cool, thanks!

Answer 2

I only have one minor nitpick: the definition of getMaxSize becomes clearer if we use logBase:

abs $ ceiling $ fromIntegral n * (log p) / (log (1 / (log 2 ^ 2)))

becomes

abs $ ceiling $ fromIntegral n * (- 0.5) * logBase (log 2) p

We can use the identity ceiling (-x) == - floor(x) to get

abs . floor $ fromIntegral n * 0.5 * logBase (log 2) p