coarbitrary for Double and Float
@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:
-
@variant m@ for large m is computed. Because the cost is O(m), it requests great time and space.
-
@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.)
Trac metadata
Trac field | Value |
---|---|
Version | 6.6 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | libraries (other) |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | Multiple |
Architecture | Multiple |