Bugfix for QuickCheck 1.1.0.0

[Patrick Perry]

"variant" takes a generator and an integer, and produces a generator.   
Here is how it works in the new version:

First, n gets written in binary:

e.g.

n = 10011

Then, we replace "1" with "fst . split". and we replace "0" with  
"snd . split".

n' = l . r . r . l . l where l = fst . split
				      r = snd . split

Then, we apply the resulting function to the generator

g' = n' g0


The run time is O (log n).

In the old version, "split" gets called n times, so the run time is  
O(n).  For certain double values, variant gets called with n on the  
order of 2^30, hence the hang in QuickCheck.  The new version of  
variant employs the same algorithm as in QuickCheck2.


Patrick


On Aug 31, 2008, at 10:53 AM, Johan Tibell wrote:

> On Sun, Aug 31, 2008 at 10:28 AM, Patrick Perry  
> <patperry at stanford.edu> wrote:
>> It's been a week and no one has objected.  I'm interpreting your  
>> silence on
>> the matter as consent.  Could someone with commit access please add  
>> the
>> patch and bump the version number for QuickCheck?
>>
>> If you haven't read the ticket, there is a bug in Quickcheck.   
>> Currently,
>> this property:
>>
>> prop_f (f :: Double -> Int) = let
>>       x = f (-3.4)
>>       in x >= 0 || x < 0
>>
>> will cause QuickCheck to hang.  The attached patch fixes the  
>> problem.  It
>> changes this:
>>
>> variant :: Int -> Gen a -> Gen a
>> variant v (Gen m) = Gen (\n r -> m n (rands r !! (v+1))
>>       where
>>               rands r0 = r1 : rands r2 where (r1, r2) = split r0
>>
>> to this:
>>
>> variant :: Int -> Gen a -> Gen a
>> variant v (Gen m) = Gen (\n r -> m n (rands r v))
>>       where
>>               rands r0 0 = r0
>>               rands r0 n = let (r1,r2) = split r0
>>                       (n',s)  = n `quotRem` 2
>>                       in case s of
>>                               0 -> rands r1 n'
>>                               _ -> rands r2 n'
>
> Could you explain how this works? It's not entirely clear to me.
>
> Thanks.
>
> -- Johan