What is a shrink, with regard to Haskell's QuickCheck?

Question

I'm learning the ropes of QuickCheck >= 2.6 but I don't understand what a shrink is. From looking at the type signature shrink looks more like expand! Please illuminate me :)

Answer 1

A single shrink is a stepwise reduction in complexity of some Arbitrary test case (an "immediate shrink"). This might be something like 2 -> 1 or 1:[] -> []. For more complex types there may be multiple ways to "incrementally shrink" a type so you specify all of them in a list.

For example, trees might be shrunk by removing any one leaf, thus if there are n leaves then shrink produces a list of length n.

Answer 2

When QuickCheck finds an input that violates a property, it will first try to find smaller inputs that also violate the property, in order to give the developer a better message about the nature of the failure.

What it means to be „small“ of course depends on the datatype in question; to QuickCheck it is anything that comes out from from the shrink function.

It is best explained in a QuickCheck session:

 Prelude Test.QuickCheck> let prop l = all (/= 5) l Prelude Test.QuickCheck> quickCheck prop *** Failed! Falsifiable (after 10 tests and 2 shrinks):     [5] 

So here QuickCheck was able to give the smallest counter-example, but judging from the comments, it first had a larger list in mind and then reduced it using shrink. To have a closer look at what is happening, we use verboseCheck:

 Prelude Test.QuickCheck> verboseCheck prop Passed:   [] Passed:  [0] Passed:   [-2,1] Passed:   [-2,2,-2] Passed:   [-4] Failed:   [-1,-2,5,4,2] *** Failed! Passed:                        [] Failed:                                        [5,4,2] Passed:                                     [] Passed:                                        [4,2] Failed:                                        [5,2] Passed:                                      [] Passed:                                        [2] Failed:                                        [5] Passed:                                      [] Passed:                                        [0] Passed:                                        [3] Passed:                                        [4] Falsifiable (after 6 tests and 3 shrinks):     [5] 

QuickCheck tries a few lists for which the proposition holds, and then finds [-1,-2,5,4,2]. Now it reduces the list, by trying sublists of it. You can convince yourself in GHCi that shrink [-1,-2,5,4,2] == [[],[5,4,2],[-1,-2,2],... and the second entry is the first that still fails the test. QuickCheck then continues with that and shrinks further: shrink [5,4,2] == [[],[4,2],[5,2],..., and further shrink [5,2] [[],[2],[5],.... Lastly it tries to shrink [5] further, but none of shrink [5] == [[],[0],[3],[4]] fail the proposition, so the final count-example is [5].