[QuickCheck] Shrinking a list

[Nick Smallbone]

Hi Jurriën,

In this example it happens that:
  * the property fails on [0,0,0]
  * the property succeeds on [0,0]
  * the property fails on [0]

The way list shrinking works is that [0,0,0] shrinks to [0,0], and
[0,0] shrinks to [0], but [0,0,0] doesn't directly shrink to [0]. So
suppose that QuickCheck has found the counterexample [0,0,0]. Then it
will try shrinking to [0,0], but the property will pass. Then
shrinking will stop and it won't even try [0]!

If the property had also failed on [0,0], then it would have carried
on to shrink [0,0] and so would find [0].

The reason why we don't make [0,0,0] directly shrink to [0] is, like
you said, to reduce the number of shrink candidates we have to try. If
a property fails on [0,0,0] and [0] it will probably fail on [0,0], so
for most properties this doesn't cause a problem. And if shrinking
really works badly, you can always define your own Arbitrary instance
that shrinks how you want.

Nick

On 20 December 2012 16:20, J. Stutterheim <j.stutterheim at me.com> wrote:
> Hi Nick,
>
>
> Thanks for the quick reply, it is really useful! In the example you mention, where the property fails for a list of length 1 and length 3, but not length 2, why does QC opt to shrink to the list of 3, instead of 1? Is this only in order to reduce the total number of shrink operations? Or there more to it?
>
>
> Jurriën
>
> On 20 Dec 2012, at 15:35, Nick Smallbone <nicsma at chalmers.se> wrote:
>
>> Hi Jurriën,
>>
>> When a property fails, QuickCheck repeats the shrinking process until
>> it can't shrink the counterexample any more. For example, if a
>> property fails on [0,1,2], QuickCheck will try each of the shrink
>> candidates ([], [1,2] etc.) in turn. If the property turns out to fail
>> on [1,2], QuickCheck will shrink that and try, among other things,
>> [1]. So you eventually get a minimal counterexample.
>>
>> This is a heuristic (e.g. if the property failed on singleton lists
>> and lists of length 3 but not on lists of length 2 then any
>> counterexample would only shrink to a list of length 3 and then stop)
>> but in practice it usually finds near-minimal counterexamples. It
>> means we avoid having to try too many shrink candidates, which would
>> slow shrinking down.
>>
>> Nick
>>
>> On 20 December 2012 14:21, Jurriën Stutterheim <j.stutterheim at me.com> wrote:
>>> Dear QC devs,
>>>
>>>
>>> I am trying to understand `shrink`'s behaviour. Let's start with a small example:
>>>
>>> Prelude Test.QuickCheck> shrink [0,1,2]
>>> [[],[1,2],[0,2],[0,1],[0,0,2],[0,1,0],[0,1,1]]
>>>
>>> In this example, where I apply `shrink` to the list `[0,1,2]`, `shrink` does not produce any singleton lists. Why is that? After all, a minimal counter-example could be found in, e.g., the list `[1]`.
>>>
>>> Thanks in advance!
>>>
>>>
>>> Jurriën
>>> _______________________________________________
>>> QuickCheck mailing list
>>> QuickCheck at projects.haskell.org
>>> http://projects.haskell.org/cgi-bin/mailman/listinfo/quickcheck
>