id,summary,reporter,owner,description,type,status,priority,milestone,component,version,resolution,keywords,cc,os,architecture,failure,difficulty,testcase,blockedby,blocking,related
1026,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.)",bug,closed,normal,Not GHC,libraries (other),6.6,fixed,QuickCheck,michal.terepeta@…,Unknown/Multiple,Unknown/Multiple,None/Unknown,Easy (less than 1 hour),,,,