[Haskell-cafe] Fwd: an idea for improving 'shrink'

[Petr Pudlák]

2014-09-05 18:22 GMT+02:00 Bryan O’Sullivan <bos at serpentine.com>:


> On Thu, Sep 4, 2014 at 1:06 PM, Petr Pudlák <petr.mvd at gmail.com> wrote:
>
>> since I got no response from the QuickCheck mail address, so I'm
>> resending it here, if someone wants to comment on the idea.
>>
>
> I don't think it pays its way: it makes shrink a bit tidier, at the cost
> of breaking backwards compatibility in a widely used library.
>
That’s a problem. But I believe it the patch addresses it. QuickCheck
always uses ‘shrink’, not ‘shrinkA’, and as the default implementation of
‘shrink’ is defined in terms of ‘shrinkA’, then it’s possible to define
instances both using ‘shrink’ and using ‘shrinkA’. So both old code and new
code that wants to take advantage of the Applicative interface work.

I believe that in the long term this change would pay off: Compare the old
code

 shrinkOne []     = []
 shrinkOne (x:xs) = [ x':xs | x'  <- shr x ]
                 ++ [ x:xs' | xs' <- shrinkOne xs ]

 shrink (x, y) =
      [ (x', y) | x' <- shrink x ]
   ++ [ (x, y') | y' <- shrink y ]

 shrink (x, y, z) =
   [ (x', y', z')
   | (x', (y', z')) <- shrink (x, (y, z)) ]

against the improved piece

traverse shr xs -- replaces the whole shrinkOne
shrinkA (x, y) = liftA2 (,) (shrinkA x) (shrinkA y)
shrinkA (x, y, z) = liftA3 (,,) (shrinkA x) (shrinkA y) (shrinkA z)

​
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140906/66f44870/attachment.html>