One hundred tests passed. Yet 58% of the input lists were empty. In the original QuickCheck manual, a demonstration of testing insertion into sorted lists exposes a problem that its success message alone cannot reveal: the program has mostly faced very easy cases.
QuickCheck, introduced by Koen Claessen and John Hughes in their 2000 paper on testing Haskell programs, automated the production of test inputs. Its documentation also showed why programmers still needed to inspect what those inputs contained.
The key design decision was to give the machine a property to check, rather than a separate expected answer for every example. That made many more tests possible. It also made the choice of examples less visible unless somebody deliberately looked.
Write the rule, then generate the examples
A property describes a relationship that a function should preserve across its inputs. Reversing a finite list twice, for instance, should return the original list. The programmer can express that relationship as a Haskell function, and QuickCheck supplies randomly generated lists on which to try it.
The manual displays a run in which this property passes 100 tests. It also gives a deliberately false property: reversing a list once leaves it unchanged. QuickCheck rejects that claim with the counterexample [-3,15]. Reversing those two different numbers changes their order.
These are results printed in the documentation, rather than experiments performed for this article. Their contrast explains the mechanism: the programmer supplies a checkable claim, and the tool searches generated examples for a case that contradicts it.
A failure can therefore raise a question about either side of the test. The implementation may be wrong, or the property may describe something the implementation was never supposed to do.
A condition can quietly reshape the sample
Consider inserting a number into a list that is already sorted. A useful property says that the resulting list should remain sorted. But this claim has a condition: the starting list must be sorted too.
The manual first expresses that condition by filtering generated lists. Unsorted candidates are discarded; sorted candidates are used to test insertion. Generation continues until enough acceptable cases have been found or an overall limit is reached.
That filtering changes the sample. Empty lists and lists with one element already satisfy the ordering condition. Longer random lists are more likely to be rejected. The test can consequently spend much of its effort checking insertion into very short lists.
The manual makes the imbalance visible by collecting list lengths. Its displayed sample contains 58% empty lists, 26% lists with one element, 13% with two, and 3% with three. Those percentages describe that documented sample, not a distribution every QuickCheck run must produce.
Combining length measurements with classifications reveals a further gap: the sample has not tested insertion at the beginning or end of a list longer than one element. The success message is accurate about the cases checked, while saying little about those missing cases.
Generate the inputs the question needs
The documentation offers a direct alternative: generate sorted lists in the first place. A custom generator supplies suitable inputs without relying on rejection to find them.
This is part of QuickCheck’s design, rather than a workaround outside it. Programmers can define generators and observe their output distributions using the library. The original paper explicitly places control of test-data distribution with the human tester.
The distinction matters because a property and a generator do different jobs. The property states what should hold. The generator determines which situations the test actually encounters. Improving one does not automatically improve the other.
The specification can need debugging too
Claessen and Hughes’s original paper describes a unification example, involving an algorithm that finds substitutions to make symbolic terms agree. They reported finding errors in its specification, even though they found no errors in the unifier itself.
One proposed property concerned repeatedly applying a substitution. It needed an additional condition excluding cyclic substitutions. Testing prompted the authors to correct what they had claimed about their code.
This is a useful consequence of making expectations executable: a counterexample can expose a misunderstanding before it becomes a confidently repeated rule.
Passing a finite collection of random tests still does not establish a property for every possible input. Joe Nelson’s later tutorial makes that boundary explicit. Hackage, the Haskell package directory, also warns that the original manual is partly outdated, so its examples should not be treated as a complete description of today’s library.
A pass count says how many cases were checked, not which ones. In the manual’s example, 100 passes sat on top of 58% empty lists, which is why the input distribution deserves as much attention as the result.
Related stories
Sources
- Koen Claessen and John Hughes: original QuickCheck project page
- Original QuickCheck manual
- Claessen and Hughes: QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs, ICFP 2000
- Joe Nelson: The Design and Use of QuickCheck, 2017
- Hackage: QuickCheck package documentation
- Featured image: Jason Scott; Wikimedia Commons; CC BY 2.0 (adapted from the original)
SIGNAL TITANS
Leave a Reply