[GHC] #1026: coarbitrary for Double and Float

[GHC]

#1026: coarbitrary for Double and Float
------------------------------------------------------------+---------------
    Reporter:  Susumu Katayama <skata at cs.miyazaki-u.ac.jp>  |       Owner:            
        Type:  bug                                          |      Status:  new       
    Priority:  normal                                       |   Milestone:            
   Component:  libraries (other)                            |     Version:  6.6       
    Severity:  normal                                       |    Keywords:  QuickCheck
  Difficulty:  Easy (1 hr)                                  |    Testcase:            
Architecture:  Multiple                                     |          Os:  Multiple  
------------------------------------------------------------+---------------
@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 at .
 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 at . (Or even the
 definition of @variant@ could be replaced.)

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1026>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler