Comparez deux fonctions à l'aide quickcheck pour générer des nombres entiers positifs

Question

Je les fonctions Haskell suivantes:

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

Et

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 

Ce que je veux faire est d'utiliser quickcheck pour comparer ces deux fonctions afin que je puisse voyez qu'ils produisent la même réponse et laquelle est la plus rapide.

Pour tester si elles ont les mêmes réponses que je veux laisser QuickCheck créer des nombres entiers positifs au hasard à l'exception de 0. Je créé une génération:

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 

Cela fonctionne à partir de la ligne de commande (ghci), mais J'ai un accessoire:

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

Et chaque fois que j'appelle cela avec QuickCheck prop_CompareAnswerExMFM il ne nous pas mon gen. Après avoir lu quelques trucs que je débrouillés que je devais définir une instance:

instance Arbitrary Integer where 
    arbitrary = positives 

Cela ne fonctionne pas car une instance arbitraire de nombre entier existent déjà. Encore une fois, après quelques googler je dis que la méthode standard pour résoudre ce problème est d'utiliser un emballage:

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 

Mais après avoir joué je continue à avoir des erreurs comme ne peut pas résoudre ce problème, Aucun cas pour (Num Positifs) découlant de le littéral '0' ou Impossible de créer une instance dérivée de 'Num Positives'.

Je pense que je fais en sorte de complexe pour ce que je veux, mais je ne peux pas le comprendre. J'espère que quelqu'un peut m'aider ou m'envoyer dans la bonne direction.

Merci

Answer 1

Le problème avec votre code est que positives la x variable a de type Integer, de sorte que vos déclarations de retour doivent inclure le constructeur Positives:

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 

Si elle aide, voici une autre façon d'écrire (un fonctionnement de même) positives fonction:

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

Ici l'appel arbitrary est un Gen Integer, donc l'argument de la fonction à fmap a le type Integer -> Positives.

Pour utiliser votre Positives newtype avec QuickCheck vous utilisez le constructeur Positives la (dé) pour obtenir les valeurs entières:

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

ghci> quickCheck prop_addtion 

Comme @Carsten mentionne dans les commentaires, QuickCheck comme un type qui a Positive a une instance arbitraire pour les types numériques et ordonnés a.