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