Improve the list shrinker

[jmid]

The current list shrinker cuts off elements one by one:

# Iter.find (fun _ -> true) (Shrink.list [1;2;3;4;5]);;
- : int list option = Some [2; 3; 4; 5]

In comparison, e.g., the Haskell shrinker (defined as shrinkList here:
https://hackage.haskell.org/package/QuickCheck-2.9.2/docs/src/Test-QuickCheck-Arbitrary.html ) will repeatedly try to remove a range of elements (before proceeding to per-entry shrinking).
It would be nice if QCheck's list shrinker could do something similar.

[c-cube]

If I read the code correctly, Haskell's shrinkList seems to try to remove blocks of size n, n/2, n/4, n/8, … where n=length l, before shrinking individual elements. To remove chunks of size k, it only cuts the list at boundaries that are multiples of k. Is that correct?

[jmid]

Yes, that is also how I read the code (but I'm no Haskeller) :-)

[c-cube]

So I tried something close to the Haskell code (although it removes chunks by a sliding window instead of partitioning). Any idea how to test this? :3

[c-cube]

I tried manually, seems fine. Please re-open if it's not sufficient or if it's perfectible.

[jmid]

Great, thanks for this! If you want a test case for this, something that forces long lists, e.g.,

let listgen = list_of_size (Gen.int_range 1000 10000) int
let t = Test.make (pair listgen listgen) (fun (xs,ys) -> List.rev (xs@ys) = (List.rev xs)@(List.rev ys))
QCheck_runner.run_tests ~verbose:true [t]

should exercise the shrinker on long lists. With the old one-by-one shrinking approach I just got:

generated; error;  fail; pass / total -     time -- test name
[✗] (   1)    0 ;    1 ;    0 /  100 --     2.1s -- anon_test_5

--- Failure --------------------------------------------------------------------

Test anon_test_5 failed (8110 shrink steps):

([0], [1])
================================================================================
failure (1 tests failed, 0 tests errored, ran 1 tests)
- : int = 1

(over 2 seconds and 8100 shrink steps in the top level)
but nevertheless resulting in a nice minimal counterexample

[c-cube]

I'll add the test and update this. Thanks!