Сравните две функции с помощью quickcheck для генерации положительных целых чисел

У меня есть следующие функции Haskell:

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

И

  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

Я хочу использовать quickCheck для сравнения этих двух функций, чтобы я мог видеть, что они дают один и тот же ответ и какая из них самая быстрая.

Чтобы проверить, есть ли у них одинаковые ответы, я хочу, чтобы QuickCheck создавал случайные положительные целые числа за исключением 0. Итак, я создал 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

Это работает из командной строки (ghci), но у меня есть опора:

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

И каждый раз, когда я вызываю это с помощью QuickCheck prop_CompareAnswerExMFM, это не соответствует моему поколению. Прочитав кое-что, я сказал, что мне нужно определить экземпляр:

  instance Arbitrary Integer where
    arbitrary = positives

Это не работает, потому что уже существует произвольный экземпляр Integer. Опять же, после некоторого поиска в Google я говорю, что стандартный способ решить эту проблему - использовать оболочку:

  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

Но после игры я продолжаю получать ошибки, например, не могу решить это, Нет экземпляра для (Num Positives), возникающего из буквального «0» или Can't make a производный экземпляр «Num Positives».

Я думаю, что усложняю то, что хочу, но я просто не могу этого понять. Я надеюсь, что кто-нибудь сможет мне помочь или направить меня в правильном направлении.

Спасибо


haskell quickcheck
person Phaeton    schedule 11.10.2015    source источник
comment
у вас уже есть это в quickcheck: Положительно ... конечно, вы должны использовать это так: prop :: Positive -> Bool, а затем prop (Positive n) = ... (разбейте его с помощью сопоставления с образцом, чтобы получить само число!) - или используйте getPositive внутри своей собственности, чтобы получить номер   -  person Random Dev    schedule 11.10.2015
comment
@carsten спасибо, я заставил это работать, используя советы, которые вы мне дали.   -  person Phaeton    schedule 11.10.2015

Ответы (2)


arrow_upward
3
arrow_downward

Проблема с вашим кодом заключается в том, что в positives переменная x имеет тип Integer, поэтому ваши операторы возврата должны включать 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

Если это поможет, вот еще один способ написать (аналогично работающую) функцию positives:

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

Здесь вызов arbitrary - это Gen Integer, поэтому аргумент функции для fmap имеет тип Integer -> Positives.

Чтобы использовать Positives newtype с QuickCheck, вы должны использовать конструктор Positives (de-) для получения значений Integer:

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

ghci> quickCheck prop_addtion

Как @Carsten упоминает в комментариях, QuickCheck как Positive a тип, который имеет произвольный экземпляр для числовых и упорядоченных типов a.

person ErikR    schedule 11.10.2015
comment
спасибо, я изменил Gen Integer на Gen Positives, но не понял, что мне также нужно было изменить x. Я отказался от идеи использовать собственный генератор, и благодаря советам @Carsten он заработал. - person Phaeton; 11.10.2015

arrow_upward
0
arrow_downward

Вот быстрый способ, который не требует особого понимания QuickCheck, но является своего рода уловкой:

prop_CompareAnswerExMFM :: Integer -> Integer -> Integer -> Bool
prop_CompareAnswerExMFM b e m =
   exMFM absB absE absM == exM absB absE absM
   where -- following guarantees args are positive integers > 0
      absB = 1 + abs b
      absE = 1 + abs e
      absM = 1 + abs m

а затем вы можете просто использовать

quickCheck prop_factored
person George Co    schedule 20.02.2019