"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

On Sun 2008-08-31 11:19, Patrick Perry wrote:

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.

I haven't looked at this in a while but I'm not sure this completely fixes things with regard to coarbitrary. That is, we can produce very simple Doubles (as defined by arbitrary) that produce (via coarbitrary) very complicated generators for other types (and there was an issue of overflow with possible sign change due to nasty casting, hence variant getting a negative argument). As I understand it, your fix to variant means that variant will return in a reasonable amount of time even with a huge argument, but it doesn't fix the issue that coarbitrary should produce a `simple' generator for a `simple' argument. I thought QC2 had a mechanism to fix this. Jed

...

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?

So are we all agreed that this should be applied, now?

Well, I'm still slightly dubious about this change, but since I'm finding it hard to articulate why, you can ignore me. Did anyone ask Koen directly about it? Or is the fact that there is a similar fix in QC2 a sufficient blessing from the original author? Regards, Malcolm

The version of QuickCheck in GHC-6.10 fixes a bug in the version bundled with GHC-6.8. Both versions of the library claim to be Quickcheck-1.1.0.0. Should someone bump the version number? Patrick This is the last time I bother anybody about this. This whole process has been far too painful. On Sep 5, 2008, at 8:44 AM, Ian Lynagh wrote:

On Sun, Aug 31, 2008 at 10:28:32AM -0700, 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?

So are we all agreed that this should be applied, now?

Patrick, could you add to http://hackage.haskell.org/trac/ghc/ticket/2535 a summary of the discussion and a link to the mailing list archives of this thread, please?

Thanks Ian