Property checks with a hand-written generator

An example-based test checks the inputs its author thought of. A property test states something that must hold for every input of a type, generates a hundred of them and looks for one that breaks the claim. The claim is usually smaller than a test: reversing a list twice gives the list back, sorting keeps the length, a decoder inverts an encoder. When one of those fails, the failing input is the report.

QuickCheck is the library that made this famous, and it is not in this image: no package, no network. The three pieces it is made of fit in a page, a generator of random values, a runner that tries many cases and a printer for the counterexample, and writing them by hand is the fastest way to see where the library earns its keep.

A claim about many inputs

The difference from the previous page is where the inputs come from. There the list of checks was written by hand, so the suite checks the cases its author had in mind. Here the checks are functions of an input, and a generator supplies inputs the author never wrote down, including the empty case and the odd spacing that breaks a parser.

A hundred cases is the number QuickCheck uses by default and a good default for a small checker: enough to hit the common shapes of a short input, few enough to run in milliseconds. A property that passes a hundred cases is not proven, it is supported, and the page shows both outcomes.

A generator without the random package

Random numbers need no library either. The generator below is splitmix64, a few lines that mix a counter into a 64-bit value: add the golden-ratio constant, multiply by a fixed odd number, shift and xor twice. The state is the counter, so a generator is a value that produces a value and the next generator, and no global state is involved:

newtype Gen = Gen Word64 next :: Gen -> (Word64, Gen) next (Gen state) = let state1 = state + 0x9E3779B97F4A7C15 mixed0 = (state1 `xor` (state1 `shiftR` 30)) * 0xBF58476D1CE4E5B9 mixed1 = (mixed0 `xor` (mixed0 `shiftR` 27)) * 0x94D049BB133111EB in (mixed1 `xor` (mixed1 `shiftR` 31), Gen state1) bounded :: Gen -> Int -> (Int, Gen) bounded gen bound = let (value, gen1) = next gen in (fromIntegral (value `mod` fromIntegral bound), gen1)

Word64 arithmetic wraps around on overflow, which is exactly what the mixing wants and why the type is not Int. bounded takes the result modulo a bound, which is biased for a bound that does not divide 2^64 and irrelevant for the sizes here.

The seed is a parameter, not a clock. Gen 42 gives the same hundred inputs on every machine and every run, so a failure found today is a failure a colleague can reproduce, and a suite that passes today passes tomorrow. That is the property people like least about real random testing and the one that matters most in a build.

Inputs for the property

A generator produces numbers; a property about strings needs strings. The input generator draws a length up to twelve and then picks each character from a small alphabet, which holds two spaces so that the awkward cases, the empty string, a leading space and a double space, all appear:

alphabet :: String alphabet = "abc " text :: Gen -> (String, Gen) text gen = let (size, gen1) = bounded gen 12 in charsOf gen1 size charsOf :: Gen -> Int -> (String, Gen) charsOf gen size = go gen size "" where go g 0 acc = (acc, g) go g remaining acc = let (index, gen1) = bounded g (length alphabet) in go gen1 (remaining - 1) (alphabet !! index : acc)

The alphabet is the place to think. Letters only would never produce the double space that breaks a word count, and a large alphabet would produce long strings with no pattern. Three letters and two spaces are enough to break the property at the end of the page within two cases.

The runner

A property is a name and a function from an input to a boolean. The runner tries the cases in order, returns the first input that fails with the number of the case it was, and stops:

data Property = Property { propertyName :: String , propertyHolds :: String -> Bool } cases :: Int cases = 100 checkProperty :: Property -> Gen -> IO Bool checkProperty property = go 1 where go :: Int -> Gen -> IO Bool go number gen | number > cases = do printf "ok - %s (%d cases)\n" (propertyName property) cases pure True | otherwise = let (sample, gen1) = text gen in if propertyHolds property sample then go (number + 1) gen1 else do printf "not ok - %s\n counterexample after %d cases: %s\n" (propertyName property) number (show sample) pure False

The type signature of the local go is not optional here. Without it GHC infers a type as general as the calls allow, and the two printf calls make that type ambiguous: the build stops with GHC-39999, "Could not deduce PrintfType". One line, go :: Int -> Gen -> IO Bool, ends the guessing.

Three properties that hold

All three claims are about lists, written as claims about strings because that is what the generator produces: a string is a list of characters, and sort works on any list of comparable values.

module Main (main) where import Control.Monad (forM) import Data.Bits (shiftR, xor) import Data.List (sort) import Data.Word (Word64) import System.Exit (exitFailure, exitSuccess) import Text.Printf (printf) newtype Gen = Gen Word64 next :: Gen -> (Word64, Gen) next (Gen state) = let state1 = state + 0x9E3779B97F4A7C15 mixed0 = (state1 `xor` (state1 `shiftR` 30)) * 0xBF58476D1CE4E5B9 mixed1 = (mixed0 `xor` (mixed0 `shiftR` 27)) * 0x94D049BB133111EB in (mixed1 `xor` (mixed1 `shiftR` 31), Gen state1) bounded :: Gen -> Int -> (Int, Gen) bounded gen bound = let (value, gen1) = next gen in (fromIntegral (value `mod` fromIntegral bound), gen1) alphabet :: String alphabet = "abc " text :: Gen -> (String, Gen) text gen = let (size, gen1) = bounded gen 12 in charsOf gen1 size charsOf :: Gen -> Int -> (String, Gen) charsOf gen size = go gen size "" where go g 0 acc = (acc, g) go g remaining acc = let (index, gen1) = bounded g (length alphabet) in go gen1 (remaining - 1) (alphabet !! index : acc) data Property = Property { propertyName :: String , propertyHolds :: String -> Bool } cases :: Int cases = 100 checkProperty :: Property -> Gen -> IO Bool checkProperty property = go 1 where go :: Int -> Gen -> IO Bool go number gen | number > cases = do printf "ok - %s (%d cases)\n" (propertyName property) cases pure True | otherwise = let (sample, gen1) = text gen in if propertyHolds property sample then go (number + 1) gen1 else do printf "not ok - %s\n counterexample after %d cases: %s\n" (propertyName property) number (show sample) pure False properties :: [Property] properties = [ Property "reversing twice is the identity" (\sample -> reverse (reverse sample) == sample) , Property "sorting keeps the length" (\sample -> length (sort sample) == length sample) , Property "sorting ignores the order of the input" (\sample -> sort sample == sort (reverse sample)) ] main :: IO () main = do results <- forM properties $ \property -> checkProperty property (Gen 42) let failed = length (filter not results) printf "%d properties, %d failed\n" (length properties) failed if failed == 0 then exitSuccess else exitFailure

ghc -Wall -O1 -o prop Prop.hs
./prop; echo "status $?"

[1 of 2] Compiling Main ( Prop.hs, Prop.o )
[2 of 2] Linking prop
ok - reversing twice is the identity (100 cases)
ok - sorting keeps the length (100 cases)
ok - sorting ignores the order of the input (100 cases)
3 properties, 0 failed
status 0

The build is clean under -Wall. hlint reports one hint and it stays, because the double reverse is the claim under test:

Prop.hs:72:21-44: Warning: Redundant reverse
Found:
reverse (reverse sample)
Perhaps:
sample
Note: increases laziness

1 hint

hlint is right about the code and wrong about the test: the property would become \sample -> sample == sample, which passes a hundred cases and checks nothing. A hint on a test is the one place where the hint is the thing to argue with.

A property that does not hold

The fourth claim is the one people write when they are counting words in their head: a text with n spaces has n + 1 words. It is true for a line of single spaces and false as soon as two spaces meet, or a space sits at either end. The generator finds that in the second case:

module Main (main) where import Control.Monad (forM) import Data.Bits (shiftR, xor) import Data.List (sort) import Data.Word (Word64) import System.Exit (exitFailure, exitSuccess) import Text.Printf (printf) newtype Gen = Gen Word64 next :: Gen -> (Word64, Gen) next (Gen state) = let state1 = state + 0x9E3779B97F4A7C15 mixed0 = (state1 `xor` (state1 `shiftR` 30)) * 0xBF58476D1CE4E5B9 mixed1 = (mixed0 `xor` (mixed0 `shiftR` 27)) * 0x94D049BB133111EB in (mixed1 `xor` (mixed1 `shiftR` 31), Gen state1) bounded :: Gen -> Int -> (Int, Gen) bounded gen bound = let (value, gen1) = next gen in (fromIntegral (value `mod` fromIntegral bound), gen1) alphabet :: String alphabet = "abc " text :: Gen -> (String, Gen) text gen = let (size, gen1) = bounded gen 12 in charsOf gen1 size charsOf :: Gen -> Int -> (String, Gen) charsOf gen size = go gen size "" where go g 0 acc = (acc, g) go g remaining acc = let (index, gen1) = bounded g (length alphabet) in go gen1 (remaining - 1) (alphabet !! index : acc) wordCount :: String -> Int wordCount = length . words data Property = Property { propertyName :: String , propertyHolds :: String -> Bool } cases :: Int cases = 100 checkProperty :: Property -> Gen -> IO Bool checkProperty property = go 1 where go :: Int -> Gen -> IO Bool go number gen | number > cases = do printf "ok - %s (%d cases)\n" (propertyName property) cases pure True | otherwise = let (sample, gen1) = text gen in if propertyHolds property sample then go (number + 1) gen1 else do printf "not ok - %s\n counterexample after %d cases: %s\n" (propertyName property) number (show sample) pure False properties :: [Property] properties = [ Property "reversing twice is the identity" (\sample -> reverse (reverse sample) == sample) , Property "sorting keeps the length" (\sample -> length (sort sample) == length sample) , Property "sorting ignores the order of the input" (\sample -> sort sample == sort (reverse sample)) , Property "the word count is one more than the number of spaces" (\sample -> wordCount sample == length (filter (== ' ') sample) + 1) ] main :: IO () main = do results <- forM properties $ \property -> checkProperty property (Gen 42) let failed = length (filter not results) printf "%d properties, %d failed\n" (length properties) failed if failed == 0 then exitSuccess else exitFailure

ghc -Wall -O1 -o prop-fail PropFail.hs
./prop-fail; echo "status $?"

[1 of 2] Compiling Main ( PropFail.hs, PropFail.o )
[2 of 2] Linking prop-fail
ok - reversing twice is the identity (100 cases)
ok - sorting keeps the length (100 cases)
ok - sorting ignores the order of the input (100 cases)
not ok - the word count is one more than the number of spaces
  counterexample after 2 cases: "a aca "
4 properties, 1 failed
status 1

words "a aca " is ["a", "aca"], two words, and the sample has two spaces, so the claim expected three. The trailing space is the second mistake in one input, and the run reports the first input that has any of them.

The counterexample is not minimal. The runner stopped at the second sample it generated, six characters long, and never tried to make it shorter. QuickCheck and its descendants shrink a failing input towards a small one, which is why their reports are usually a single character or an empty list. Here the reader has to look at "a aca " and see the trailing space, which is enough for this page and would not be enough for a suite of fifty properties.

What this checker does not do

Three things separate this from a real property library, and all three are work rather than magic. Shrinking is the first: a failing input is reduced while it still fails, so the report is the smallest input that shows the bug. Type-driven generation is the second: with a class Arbitrary every property gets a generator from the type of its argument, and a new type needs one instance instead of one function per property. Distribution is the third: a generator that returns the empty string half the time tells you very little about long inputs.

The next page puts checks of the first page into a Cabal test-suite, so that cabal test --offline builds and runs them and reads the exit status. The page on the tools that are not here covers QuickCheck, HUnit, hspec, tasty and doctest, with the resolver error for a package that is missing. The course lesson on random numbers without the random package builds a linear congruential generator for the same reason.

The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev