Produces a (possibly) empty list of all the possible immediate shrinks
of the given value.
The default implementation returns the empty list, so will not try to
shrink the value. If your data type has no special invariants, you can
enable shrinking by defining
shrink = genericShrink,
but by customising the behaviour of
shrink you can often get
simpler counterexamples.
Most implementations of
shrink should try at least three
things:
- Shrink a term to any of its immediate subterms. You can use
subterms to do this.
- Recursively apply shrink to all immediate subterms. You can
use recursivelyShrink to do this.
- Type-specific shrinkings such as replacing a constructor by a
simpler constructor.
For example, suppose we have the following implementation of binary
trees:
data Tree a = Nil | Branch a (Tree a) (Tree a)
We can then define
shrink as follows:
shrink Nil = []
shrink (Branch x l r) =
-- shrink Branch to Nil
[Nil] ++
-- shrink to subterms
[l, r] ++
-- recursively shrink subterms
[Branch x' l' r' | (x', l', r') <- shrink (x, l, r)]
There are a couple of subtleties here:
- QuickCheck tries the shrinking candidates in the order they appear
in the list, so we put more aggressive shrinking steps (such as
replacing the whole tree by Nil) before smaller ones (such as
recursively shrinking the subtrees).
- It is tempting to write the last line as [Branch x' l' r' | x'
<- shrink x, l' <- shrink l, r' <- shrink r] but this is
the wrong thing! It will force QuickCheck to shrink x,
l and r in tandem, and shrinking will stop once
one of the three is fully shrunk.
There is a fair bit of boilerplate in the code above. We can avoid it
with the help of some generic functions. The function
genericShrink tries shrinking a term to all of its subterms
and, failing that, recursively shrinks the subterms. Using it, we can
define
shrink as:
shrink x = shrinkToNil x ++ genericShrink x
where
shrinkToNil Nil = []
shrinkToNil (Branch _ l r) = [Nil]
genericShrink is a combination of
subterms, which
shrinks a term to any of its subterms, and
recursivelyShrink,
which shrinks all subterms of a term. These may be useful if you need
a bit more control over shrinking than
genericShrink gives you.
A final gotcha: we cannot define
shrink as simply
shrink x = Nil:genericShrink x as this shrinks
Nil to
Nil, and shrinking will go into an infinite
loop.
If all this leaves you bewildered, you might try
shrink =
genericShrink to begin with, after deriving
Generic for your type. However, if your data type has any
special invariants, you will need to check that
genericShrink
can't break those invariants.