Haskell Hspec/Quickcheck test for numeric function

Question

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
                             

Answer 1

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
      ...