Dependent shrinking in QuickCheck

Question

I'm faced with the problem of writing a shrinking function for a generator that depends of the value (s) output by another one. Basically a generator of the form:

do
  a <- genA
  b <- f a
  pure $! g a b

where genA :: Gen a, f :: a -> Gen b g :: a -> b -> c. For the sake of argument assume g = (,). Then the problem is that given a pair (a, b), shrinking a could break the relation that exists between a, f and b.

To give an example of this, consider the following lists with a cached length:

data List =
  List
  { llength :: Int
  , list :: [Int]
  } deriving (Eq, Show)

The arbitrary function can be easily defined:

instance Arbitrary List where
  arbitrary = do
    n <- choose (0, 10)
    xs <- vector n
    pure $! List { llength = n, list = xs }

however shrinking an element of the form List n xs requires some knowledge of the relation between n and xs.

In the preceding example this isn't a problem, since the relation between n and xs is easy to determine, however for the problem I'm working on determining this relationship is not trivial.

Libraries like hedgehog that feature integrated shrinking would solve this particular problem (albeit not always), however I'm wondering if there is a principled way to solve this in QuickCheck.

---

Here is an example that shows how hedgehog finds the minimal counterexample for the property that the length of the list is less than 5 (it consistently gives List 5 [ 0 , 0 , 0 , 0 , 0 ] as counterexample). And here is an example of how I (think I) solved this problem at the moment, basically by emulating integrated shrinking.

Also, be aware that the the behavior of the monadic interface of hedgehog is probably not what you want most of the time.

Answer 1

There is no panacea. To the best of my knowledge, integrated shrinking is the state of the art of general purpose solutions, with the caveats you mention. It's built into Hedgehog, but the approach is also 100% compatible with QuickCheck, which simply takes a neutral stance on the matter of shrinking, because there is no solution even close to a one-size-fits-all.

Libraries like hedgehog that feature integrated shrinking would solve this particular problem (albeit not always), however I'm wondering if there is a principled way to solve this in QuickCheck.

The question suggests that there is some kind of methodological dichotomy between Hedgehog and QuickCheck, but that's not the case. They follow different design philosophies, but they're not opposed at all.

Integrated shrinking (i.e., mixing generation and shrinking in the same monad) is at a sweet spot of generality and convenience; it is built into Hedgehog, but one could also build something equivalent on top of QuickCheck. There's no fundamental obstacle, it's just not worth the effort compared to simply using what's already there in Hedgehog.

QuickCheck is organized differently, with a separate generator Gen a and shrinker a -> [a]. If you want to generate a tree of values and use that for shrinking (which is how integrated shrinking works), you are free to go ahead and just do it. The point is, the choice is yours to make, instead of made for you implicitly; in exchange, you get to start with two simple abstractions for orthogonal concepts (generation and shrinking), instead of one more complex abstraction tying the two concepts together. Pragmatically, the difference is superficial and it's easy enough to decompose or merge back these abstractions explicitly.