# Ticket #1026 (closed bug: fixed)

Opened 6 years ago

## coarbitrary for Double and Float

Reported by: Owned by: Susumu Katayama normal Not GHC libraries (other) 6.6 QuickCheck michal.terepeta@… Unknown/Multiple Unknown/Multiple None/Unknown Easy (less than 1 hour)

### Description

@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

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.)

## Change History

### Changed 6 years ago by Susumu Katayama <skata@…>

patch fixing the bug

### Changed 6 years ago by igloo

• milestone set to Not GHC

### Changed 5 years ago by simonmar

• architecture changed from Multiple to Unknown/Multiple

### Changed 5 years ago by simonmar

• os changed from Multiple to Unknown/Multiple

### Changed 4 years ago by simonmar

• difficulty changed from Easy (1 hr) to Easy (less than 1 hour)