Remix.run Logo
Remix clone Hacker News
new | show | ask | jobsGithub
▲ chriswarbo 10 hours ago

QuickCheck won't preserve invariants, since its shrinkers are separate from its generators. For example:

    data Rat = Rat Int Nat deriving (Eq, Show)

    genRat = do
      (num, den) <- arbitrary
      pure (Rat num (1 + den))
`genRat` is a QuickCheck generator. It cannot do shrinking, because that's a completely separate thing in QuickCheck.

We can write a shrinker for `Rat`, but it will have nothing to do with our generator, e.g.

    shrinkRat (Rat num den) = do
      (num', den') <- shrink (num, den)
      pure (Rat num' den')
Sure, we can stick these in an `Arbitrary` instance, but they're still independent values. The generation process is essentially state-passing with a random number generator; it has nothing to do with the shrinking process, which is a form of search without backtracking.

    instance Arbitrary Rat where
      arbitrary = genRat
      shrink = shrinkRat
In particular, `genRat` satisfies the invariant that values will have non-zero denominator; whereas `shrinkRat` does not satisfy that invariant (since it shrinks the denominator as an ordinary `Nat`, which could give 0). In fact, we can't even think about QuickCheck's generators and shrinkers as different interpretations of the same syntax. For example, here's a shrinker that follows the syntax of `genRat` more closely:

    shrinkRat2 (Rat n d) = do
      (num, den) <- shrink (n, d)
      pure (Rat num (1 + den))
This does have the invariant that its output have non-zero denominators; however, it will get stuck in an infinite loop! That's because the incoming `d` will be non-zero, so when `shrink` tries to shrink `(n, d)`, one of the outputs it tries will be `(n, 0)`; that will lead to `Rat n 1`, which will also shrink to `Rat n 1`, and so on.

In contrast, in Hypothesis, Hedgehog, falsify, etc. a "generator" is just a parser from numbers to values; and shrinking is applied to those numbers, not to the output of a generator. Not only does this not require separate shrinkers, but it also guarantees that the generator's invariants hold for all of the shrunken values; since those shrunken values have also been outputted by the generator (when it was given smaller inputs).