3
\$\begingroup\$

I'm learning to use HSpec and QuickCheck. As example I was implementing the Pseudocode from Wikipedia:Extended Euclidean Algorithm. You can find the project at github for the implementation of the tested code.

In particular I wonder about two practices:

  • selection of test cases - I took two trivial samples, examples from the wikipedia page and took three property tests.
  • Generation of cases - the a>0 && b>0 seems inefficient to me.

I'm most interested what would be a good practice to confirm two algorithms produce the same results.

module EuclidSpec  ( spec )
where

import Test.Hspec
import Test.Hspec.Core.QuickCheck
import Test.QuickCheck
import Lib

spec :: Spec
spec = do
  describe "Trivial" $ do
    it "trivial example 99 1" $
       let trivial = extendedEuclid 99 1
       in  trivial `shouldBe` (EuclidRes 1 (0) 1)
    it "trivial example 99 99" $
       let trivial = extendedEuclid 99 99
       in  trivial `shouldBe` (EuclidRes 99 (0) 1)
  describe "Examples" $ do
    it "explanation example 99 78" $
       let wikiExample = extendedEuclid 99 78
       in  wikiExample `shouldBe` (EuclidRes 3 (-11) 14)
    it "explanation example flipped 78 99" $
       let wikiExample = extendedEuclid 78 99
       in  wikiExample `shouldBe` (EuclidRes 3 14 (-11) )
    it "explanation example 99 78" $
       let wikiExample = extendedEuclid 240 46
       in  wikiExample `shouldBe` (EuclidRes 2 (-9) 47)
  describe "properties" $ do
      it "both numbers divisible a%gcd == 0, b%gcd ==0" $ property $
            prop_divisible
      it "bezout a*s+b*t = gcd" $ property $
            prop_bezout
      it "recursive and iterative algorithm have same result" $ property $
            prop_same_as_recursive

prop_divisible a b = a>0 && b>0 ==> a `mod` d ==0 && b `mod`d == 0
  where EuclidRes d s t = extendedEuclid a b
                             
prop_bezout a b = a>0 && b>0 ==> a*s + b*t == d
  where EuclidRes d s t = extendedEuclid a b

prop_same_as_recursive a b = a>0 && b>0 ==> extendedEuclid a b == extendedEuclid' a b
                             
\$\endgroup\$
3
\$\begingroup\$

Ah, a fine Spec. Has been a while since I've used Hspec, but your tests seem reasonable. So, first of all: well done!

There is one bit we should fix though, and you have identified it yourself: the property tests.

QuickCheck's newtypes

Creating any kind of number and then checking whether it's positive is a hassle, as half the numbers will get discarded per candidate. However, since Hspec uses QuickCheck, we can use Positive to only generate positive numbers:

prop_divisible (Positive a) (Positive b) =  a `mod` d == 0 && b `mod`d == 0
  where EuclidRes d s t = extendedEuclid a b

Other than that there are no more objective improvements.

However, there are some personal I would use in my own specs.

Reduce let … in … bindings in specs

Consider the following spec

  describe "Trivial" $ do
    it "trivial example 99 1" $
       let trivial = extendedEuclid 99 1      
       in  trivial `shouldBe` (EuclidRes 1 (0) 1)

If I want to understand the spec, I have to read the first line, remember the value of trivial (and that it hasn't been changed after calling extendedEuclid), and supply it in the next one.

If I instead write

  describe "Trivial" $ do
    it "trivial example 99 1" $
       extendedEuclid 99  1 `shouldBe` (EuclidRes 1 (0) 1)
-- or
    it "trivial example 99 99" $
       extendedEuclid 99 99 
           `shouldBe` (EuclidRes 99 (0) 1)

I immediately see that extendedEucild is getting tested. This also fits the official style, where let … in … bindings aren't used at all.

Other small pieces

You can use prop from Test.Hspec.QuickCheck instead of it "..." $ property $ ...:

import Test.Hspec.QuickCheck

...

  describe "properties" $ do
      prop "both numbers divisible a%gcd == 0, b%gcd ==0" $ 
            prop_divisible
      ...
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.