Re: Bugfix for QuickCheck 1.1.0.0

31 Aug 2008

      "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  
 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