Shrinking optimisations

[kderme]

I was trying to implement an optimization for shrinking and I may need a bit of feedback. The idea is the following: running a test for a random element can give feedback about how to shrink efficiently in case of failure. If, for example, the element is a list and we test it by folding until some codition fails, it may be enough to shrink only the failing prefix. I think there is not much support for something like this, so I tried to implement it myself. The pure case was pretty straight forward:

shrinking' :: Testable prop =>
              ((b, a) -> [a])  -- ^ 'shrink'-like function.
           -> a                -- ^ The original argument
           -> (a -> (prop, b)) -> Property

based on the existing shrinking.

The monadic case was more tricky. I played a bit with the types and the result was this monstrosity (EDIT: there is an improved version below):

shrinking'' :: forall a b prop. Testable prop =>
               ((b, a) -> [a])  -- ^ 'shrink'-like function.
            -> a                -- ^ The original argument
            -> (a -> Gen (IO (prop, b))) -> Property
shrinking'' shrinker x0 pf = rose' $ props x0
  where
      props :: a -> Rose Property
      props x =
       let
          res = pf x
          prop = property $ ioProperty . fmap fst <$> res
          ls = fmap (\t -> props <$> shrinker (snd t, x)) <$> res
          rose :: Gen (IO (Rose Property)) = fmap (\ls -> MkRose prop ls) <$> ls
          prop' = property $ fmap (rose' . IORose) rose
       in MkRose prop' []

rose' :: Rose Property -> Property
rose' r = MkProperty (fmap (MkProp . joinRose . fmap unProp) (promote (unProperty <$> r)))

I tested it on monadic examples in https://github.com/advancedtelematic/quickcheck-state-machine and it surprisingly worked, but I can see that there are many violations (like the usage of IORose).

What's your opinion on this? Does it look like a sane idea and would you be interested to have it in QuickCheck?

[kderme]

I think I found an improved way to write this, which doesn't use IORose and generalises IO

shrinking'' :: Testable prop
            => Monad m
            => (m Property -> Property)
            -> ((b, a) -> [a])  -- ^ 'shrink'-like function.
            -> a                -- ^ The original argument
            -> (a -> Gen (m (prop, b))) -> Property
shrinking'' runner shrinker x0 pf = rose' $ props x0
  where
      props x =
       let
          res = pf x
          p = property $ runner . fmap (property . fst) <$> res
          ls = fmap (\t -> props <$> shrinker (snd t, x)) <$> res
          p' = property $ runner . fmap (rose' . MkRose p) <$> ls
       in MkRose p' []

rose' :: Rose Property -> Property
rose' r = MkProperty (fmap (MkProp . joinRose . fmap unProp) (promote (unProperty <$> r)))

[MaximilianAlgehed]

Much (all?) of this functionality is already present in the form of the Shrinking combinator for adding state to shrinkers. Introducing a more convenient interface for Shrinking is covered by issue #273 so I'm going to close this as duplicate.