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

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].

Answer 2

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.