How do I get good (small) shrinks out of QuickCheck?

Question

I'm trying to run QuickCheck on some nested lists, something that looks like this:

type Constraint = Text
data Value = Value [Constraint]
data Literal = Literal Value [Value]
type Formula = [Literal]

So a formula is a list of literals, each of which contains a predicate and some arguments; predicate/arguments are values which are a disjunction of constraints in string form each. That gives us a list of lists of lists of lists, phew!

If one of my QuickCheck properties fails, I tend to get an incomprehensible pageful of output. Before experimenting with shrink, I used to get around this by having arbitrary instances that could only generate a small set of (small) values. Implementing the shrink function for each of my types seems to help a little, but not as much as I'd like. I still get a pageful of output.

I think what I want from shrink is a small list of literals, where each literal has a small list of values, which in turn has few constrains, each of which is as short as possible. But in my current efforts, at least of these lists gets big enough to make the output horrible. If I try to tune my shrink implementations, I also find that QC starts taking a very long time (searching for shrinks?), which kind of dampens my efforts to shrink effectively.

How do you improve your chances of understanding QuickCheck failures when you have nested data like this?

Answer 1

FWIW, have a look at https://github.com/leepike/SmartCheck, which claims to derive better shrinks than one can usually do manually.

Answer 2

I had a similar problem, but I was using C and home made example generator :) I had slow and correct, and fast and incorrect implementation.

Using random examples, when you find incorrect example, I would suggest shrinking of example itself. (This, of course, could or should, be done by program, instead of by computer)

If you have predicate for this test, and you have example that does not work, try eliminating elements form lists, of all orders (this should be linear order of magnitude of callings) and for each try if it fails the test.

If it is still failing, there is no reason for keeping this in example.

If it starts passing, then this element should stay in reduced example.

(This is greedy and not optimal, but it does execute in poly, instead of exponential time, and it worked for me)

For more scientific look, I suggest chapter "Simplifying problems" from the book "WHY PROGRAMS FAIL: A Guide to Systematic Debugging" by A.Zeller.

Note: this is mostly what shrink does...