O'Reilly logo

Real World Haskell by Donald Bruce Stewart, Bryan O'Sullivan, John Goerzen

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Testing with QuickCheck

Before we pay any attention to performance, we want to establish that our Bloom filter behaves correctly. We can easily use QuickCheck to test some basic properties:

-- file: examples/BloomCheck.hs
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
module Main where

import BloomFilter.Hash (Hashable)
import Data.Word (Word8, Word32)
import System.Random (Random(..), RandomGen)
import Test.QuickCheck
import qualified BloomFilter.Easy as B
import qualified Data.ByteString as Strict
import qualified Data.ByteString.Lazy as Lazy

We will not use the normal quickCheck function to test our properties, as the 100 test inputs that it generates do not provide much coverage:

-- file: examples/BloomCheck.hs
handyCheck :: Testable a => Int -> a -> IO ()
handyCheck limit = check defaultConfig {
                     configMaxTest = limit
                   , configEvery   = \_ _ -> ""
                   }

Our first task is to ensure that if we add a value to a Bloom filter, a subsequent membership test will always report it as present, regardless of the chosen false positive rate or input value.

We will use the easyList function to create a Bloom filter. The Random instance for Double generates numbers in the range zero to one, so QuickCheck can nearly supply us with arbitrary false positive rates.

However, we need to ensure that both zero and one are excluded from the false positives we test with. QuickCheck gives us two ways to do this:

Construction

We specify the range of valid values to generate. QuickCheck provides a forAll combinator for ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required