coarbitrary for Double and Float

[Susumu Katayama <skata@…>]

@coarbitrary@ methods for Double and Float defined in Test.QuickCheck? are not usable.

With GHC 6.6 they either consume unrealistically great amount of time and space, or cause: *** Exception: Prelude.(!!): negative index

With the HEAD compiler, it soon causes great heap consumption and soon fails with stack overflow.

Example:

The following code gobbles the heap space quickly, so please set the maximum heap size limit, or be prepared to press CTRL-C when trying it.

\begin{code}
import Test.QuickCheck
import Control.Monad.Fix(fix)

instance Show (a->b) where
    showsPrec _ f = ("fun"++)

cata (x,f) 0 = x
cata (x,f) i = f (cata (x,f) (i-1))

kata c (x,f) 0 = x
kata c (x,f) i = f (c (x,f) (i-1))

prop_cata :: (Eq a, Show a) => Int -> a -> (a->a) -> Property
prop_cata = \i x f -> i>=0 ==> cata (x,f) i == fix kata (x,f) i

main = do verboseCheck (prop_cata :: Int -> Int   -> (Int  ->Int)   -> Property)
          verboseCheck (prop_cata :: Int -> Float -> (Float->Float) -> Property)
\end{code}

(There can be a simpler example, but I do not think that is necessary because I have already tracked down the problem.)

Reason:

The coarbitrary methods for Float and Double are defined as:

  coarbitrary x = coarbitrary (decodeFloat x)

where the first return value (:: Integer) of @decodeFloat :: a -> (Integer,Int)@ usually exceeds @maxBound::Int@. It will eventually be converted into Int while computing the coarbitrary method for Integer, defined as:

  coarbitrary n = variant (fromInteger (if n >= 0 then 2*n else 2*(-n) + 1))

Because @(if n >= 0 then 2*n else 2*(-n) + 1)@ exceeds @maxBound::Int@, either of the following usually happens:

1) @variant m@ for large m is computed. Because the cost is O(m), it requests great time and space.

2) @variant m@ for negative m is requested, and that causes the "(!!): negative index" error.

Solution:

@variant m@ could be computed in O(log m), for example,

logvariant :: Integral i => i -> Gen a -> Gen a
logvariant 0 = variant 0
logvariant n | n > 0 = logvariant (n `div` 2) . variant (fromIntegral (n `mod` 2)) . variant 1
             | otherwise = error "logvariant: negative argument"

Also, negative arguments should be dealt with correctly, thus:

newvariant :: Integral i => i -> Gen a -> Gen a
newvariant n | n >= 0    = logvariant n      . variant 0
             | otherwise = logvariant (-1-n) . variant 1
instance Arbitrary Integer where
	arbitrary = ...
	coarbitrary = newvariant

I enclose a patch for doing the above. I minimized the affected parts, but coarbitrary for Int could also be replaced with @newvariant@. (Or even the definition of @variant@ could be replaced.)

[Susumu Katayama <skata@…>]

patch fixing the bug

[michalt]

It seems to be fixed in the current QC, but I've had only a quick look at the code so it'd be great if you could confirm whether the problem is still present. Thanks!

[igloo]

Either way, QuickCheck? no longer comes with GHC, so I'll close this ticket.