Why does shrinking stop once one of the terms is fully shrunk

Question

I'm looking at the comments in shrink:

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.

I'm a bit puzzled about this, I thought that the problem with that shrink was that we're taking the cartesian product of the shrinks of the subterms, which might be quite large. I don't get why shrinking will stop once one of the three is fully shrunk.

So in other words, I thought the definition above would compute all combinations of shrinks of x, l, and r, but I wouldn't expect shrink to stop once one the the terms is fully shrunk.

Answer 1

The proposed code is wrong, because we only consider shrinks that shrink all three of the terms by at least one step. To see the problem, imagine all three candidates are Int:

x = 1
l = 0
r = 2

Then we have

shrink x = [0]
shrink l = []
shrink r = [1, 0]

A nested list comprehension over these three lists will yield no values, because no suitable candidate for l can be found. So we never try some valid shrinks like (0, 0, 1). The shrink instance for tuples does the right thing (suggesting each shrink where at least one term can be shrunk), so mapping over that solves the problem.