[darcs-devel] [patch1979] better shrinking for patches

[Ganesh Sittampalam]

Ganesh Sittampalam <ganesh at earth.li> added the comment:

On 24/02/2020 08:16, Ben Franksen wrote:

>> The instances for sequences actually drop patches.
> 
> I must be missing something because I don't see that they do.

For example:

> instance (Commute p, Shrinkable p) => Shrinkable (FL p) where
[...]
>   shrinkAtStart ps = do
>     q :> qs <- headPermutationsFL ps
>     FlippedSeal qs:map (mapFlipped (:>: qs)) (shrinkAtStart q)

The first shrink result is 'FlippedSeal qs' which omits one of the
patches from 'ps'.

> My remark was not about performance at all. I think QC assumes that the
> shrink list is sorted by "size" (increasing) and /stops/ searching at
> the first element that fails the test. In my book this means that not
> starting the result list with the smallest possible shrinking means that
> shrinking will not give the best possible results.
> 
> It is quite possible that I am confused about how shrinking works. If
> that is the case please enlighten me.

Shrinking is iterative and a shrink function is only expected to produce
"immediate" shrinks. For one iteration, QC will take the first shrink
that fails the test, but then will attempt to further shrink that
result. It will only terminate if there are *no* shrinks that fail the test.

So any final result from shrinking will be locally minimal: there will
be no further shrinks possible to that value. There certainly could be
weird failures where e.g. lists of size 4 and 6 fail, but none of size
5, and so we'd get stuck at 6 if we just shrink by 1 element each time.
But more of the time it's just about performance, i.e. the faster we
find smaller shrinks the less work we do.

__________________________________
Darcs bug tracker <bugs at darcs.net>
<http://bugs.darcs.net/patch1979>
__________________________________