Compare two functions using quickcheck to generate positive integers

Question

I have the following Haskell functions:

  expM ::  Integer -> Integer -> Integer -> Integer
  expM x y = rem (x^y)

And

  exMME :: Integer -> Integer -> Integer -> Integer
  exMME b 0 m = 1
  exMME b e m = exMME' b e m 1 0 where    
    exMME' b e m c e'        
      | e' < e = exMME' b e m ((b * c) `mod` m) (e'+1)
      | otherwise = c

What I want to do is use quickCheck to compare these two functions so i can see that they produce the same answer and which one is the fastest.

To test if they have the same answers I want to let QuickCheck create random positive integers with the exception of 0. So I created a Gen:

positives :: Gen Integer
  positives = 
    do -- Pick an arbitrary integer:
      x <- arbitrary    
      if (x == 0) 
        then return 1
      else if (x < 0)
        then return (-x)
      else 
        return x

This works from the command line (ghci) but I have a prop:

  prop_CompareAnswerExMFM :: Integer -> Integer -> Integer -> Bool
  prop_CompareAnswerExMFM b e m =exMFM b e m == exM b e m

And each time i call this with QuickCheck prop_CompareAnswerExMFM it doesn't us my gen. After reading some stuff i toughed that i needed to define a instance:

  instance Arbitrary Integer where
    arbitrary = positives

This doesn't work because a arbitrary instance of Integer already exist. Again after some googling I say that the standard way to solve this is to use a wrapper:

  newtype Positives = Positives Integer
    deriving (Eq, Ord, Show)

  instance Arbitrary Positives where
    arbitrary = positives

  positives :: Gen Positives
  positives = 
    do -- Pick an arbitrary integer:
      x <- arbitrary    
      if (x == 0) 
        then return 1
      else if (x < 0)
        then return (-x)
      else 
        return x

But after playing around i keep getting errors like can't resolve this, No instance for (Num Positives) arising from the literal '0' or Can't make a derived instance of 'Num Positives'.

I think i'm making it way to complex for what i want but I just can't figure it out. I hope someone can help me or send me in the right direction.

Thanks

you already have this in quickcheck: Positive ... of course you should use it like this: prop :: Positive -> Bool and then prop (Positive n) = ... (deconstruct it with patternmatching to get out the number itself!) - or use getPositive inside your property to get the number — Random Dev

ErikR ErikR · Accepted Answer · 2015-10-11T13:44:13

The problem with your code is that in positives the variable x has type Integer, so your return statements need to include the Positives constructor:

positives :: Gen Positives
positives =
   do -- Pick an arbitrary integer:
     x <- arbitrary
     if (x == 0)
       then return $ Positives 1
     else if (x < 0)
       then return $ Positives (-x)
     else
       return $ Positives x

If it helps, here is another way to write (a similarly working) positives function:

positives' :: Gen Positives
positives' = fmap (\x -> Positives (1 + abs x)) arbitrary

Here the arbitrary call is a Gen Integer, so the function argument to fmap has type Integer -> Positives.

To use your Positives newtype with QuickCheck you would use the Positives (de-)constructor to get at the Integer values:

prop_addition :: Positives -> Positives -> Bool
prop_addition (Positives a) (Positives b) = a + b >= 2

ghci> quickCheck prop_addtion

As @Carsten mentions in the comments, QuickCheck as a Positive a type which has an arbitrary instance for numeric and ordered types a.

Compare two functions using quickcheck to generate positive integers

2 Answers