CSE399: Advanced ProgrammingHandout 18QuickCheckOverviewQuickCheck is a lightweight tool for random testing ofHaskell programs, developed by Koen Claess en and JohnHughes.•Based on specifications of desired properties, expressedas Haskell functions•Properties are verified on randomly generated test data.•The class system is used in clever ways to makeeverything look simple.A Simple Property of Listsprop_RevApp :: [Int] -> [Int] -> Boolprop_RevApp xs ys =reverse (xs ++ ys) == reve rse ys ++ reverse xsA Simple Property of Listsprop_RevApp :: [Int] -> [Int] -> Boolprop_RevApp xs ys =reverse (xs ++ ys) == reve rse ys ++ reverse xsPrelude Main> Quickcheck.qu ickCheck prop_RevAppOK, passed 100 tests.A Simple Property of Listsprop_RevApp :: [Int] -> [Int] -> Boolprop_RevApp xs ys =reverse (xs ++ ys) == reve rse ys ++ reverse xsPrelude Main> Quickcheck.qu ickCheck prop_RevAppOK, passed 100 tests.N.b.: the type declaration on the property is require d here,because we need to restrict its type to a particular instance— only monomorphic properties can be checked byQuickCheck.A Bad PropertySuppose we mess up the specification:prop_BadRevApp :: [Int] -> [Int] -> Boolprop_BadRevApp xs ys =reverse (xs ++ ys) == reve rse xs ++ reverse ysA Bad PropertySuppose we mess up the specification:prop_BadRevApp :: [Int] -> [Int] -> Boolprop_BadRevApp xs ys =reverse (xs ++ ys) == reve rse xs ++ reverse ysPrelude Main> Quickcheck.qu ickCheck prop_BadRevAppFalsifiable, after 4 tests:[-3,-4,-4][-4,-1,1,1]Conditional Properti e sMany properties are not true universally (for all inputs ofappropriate types), but only for inputs satisfying someconditions.ins :: Or d a => a -> [a] -> [a]ins a [] = [a]ins a (a’:as) = if a < a’then a:a’:aselse a’:(ins a as)ordered :: Ord a => [a] -> Boolordered (a:a’:as) = (a<=a’) && (order ed (a’:as))ordered _ = Trueprop_BadIns :: Int -> [Int] -> Bo olprop_BadIns a as = ordered (ins a as)Conditional Properti e sPrelude Main> Quickcheck.qu ickCheck prop_BadInsFalsifiable, after 9 tests:4[5,-3]Conditional Properti e sWe can make a property conditional by writing it as<condition> ==> <property>:prop_Ins :: Int -> [Int] -> Propertyprop_Ins a as = (ordered as) ==> (or dered (ins a as))Prelude Main> Quickcheck.qu ickCheck prop_InsOK, passed 100 tests.Conditional Properti e sWe can make a property conditional by writing it as<condition> ==> <property>:prop_Ins :: Int -> [Int] -> Propertyprop_Ins a as = (ordered as) ==> (or dered (ins a as))Prelude Main> Quickcheck.qu ickCheck prop_InsOK, passed 100 tests.Note that the result type of prop_Ins has changed fromBool to P roperty. This is because the “testing semantics” ofconditional properties is a little more tricky than for simpleproperties.A Pi tfall of Condit ional Proper tiesinsWrong :: Ord a => a -> [a] -> [a]insWrong a [] = [a]insWrong a as| (length as) == 6 = as ++ [a]| otherwise = ins a asprop_InsWrong :: Int -> [Int] - > Propertyprop_InsWrong a as =(ordered as) == > (ordered (insWrong a as))Prelude Main> Quickcheck.qu ickCheck prop_InsWrongOK, passed 100 tests.What Went Wrong?QuickCheck provides combinators for investigating thedistribution of test cases.collect :: a -> b -> Propertyclassify :: Boo l -> String -> a -> Propertytrivial :: Bool -> a -> PropertyTo see information about distribution, use verboseCheckinstead of quickCheck.prop_InsWrong’ :: Int -> [Int] -> Prop ertyprop_InsWrong’ a as =(ordered as) == >collect (length as) $classify (ordered (a :as)) "at-head" $classify (ordered (a s++[a])) "at-tail" $(ordered (insWrong a as))Prelude Main> Quickcheck.ve rboseCheck prop_InsWrong’...OK, passed 100 tests.42% 0, at -head, at-tail.12% 1, at -tail.11% 2, at -tail.9% 2, at-head.7% 2.7% 1, at-head.6% 1, at-head, at-tail.2% 3, at-tail.2% 3.1% 4, at-head.1% 3, at-head.Fixing t he distribution — First tryWe can try to fix the distribution by addi ng anothercondition:prop_InsWrong’’ :: Int -> [Int] -> Propertyprop_InsWrong’’ a as =(ordered as) && (length as >= 5) ==>(ordered (insWrong a as))Fixing t he distribution — First tryWe can try to fix the distribution by addi ng anothercondition:prop_InsWrong’’ :: Int -> [Int] -> Propertyprop_InsWrong’’ a as =(ordered as) && (length as >= 5) ==>(ordered (insWrong a as))However:Prelude Main> Quickcheck.qu ickCheck prop_InsWrong’’Arguments ex hausted after 0 tests.Generating Random Test Dataclass Ar bitrary a wherearbitrary :: Gen aGenerating Random Test Dataclass Ar bitrary a wherearbitrary :: Gen aQuickCheck provides generators for most base types suchas Int, Char, Fl oat, and lists.QuickCheck also provides combinators for building customgenerators...Generating Random Test Datanewtype Gen a = Gen (Rand -> a)-- (roughly; in fact, Gen i s an abstract t ype)choose : : (Int,Int) -> Gen Intoneof :: [Gen a] -> Gen aoneof [r eturn Heads, retu rn Tails]frequency :: [(Int, Gen a)] -> Gen afrequency [( 1, re turn Heads), (2, return Tails)]etc...N.b.: The returns here are because Gen is a monad.Generating Random Test DataWe can use these primitives to build generators for a varietyof types. E.g. ...instance Arbitrary I nt wh erearbitrary = choose (- 20,20)instance (Arbitrary a, Arbi trary b)=> Arbitrary (a,b) wh erearbitrary = liftM2 (, ) arbitrary arbitraryA Custom Gene rator for Ordered ListsorderedList =do a <- frequen cy[(1, return []) ,(7, liftM2 (:) arbitrary arbitrary)]return (sort a)prop_InsWrong’’’ :: Int -> Pro pertyprop_InsWrong’’’ a =forAll o rderedList $ \ as -> ordered (insWr ong a as )A Custom Gene rator for Ordered ListsorderedList =do a <- frequen cy[(1, return []) ,(7, liftM2 (:) arbitrary arbitrary)]return (sort a)prop_InsWrong’’’ :: Int -> Pro pertyprop_InsWrong’’’ a =forAll o rderedList $ \ as -> ordered (insWr ong a as )Prelude Main> Quickcheck.qu ickCheck prop_InsWrong’’’Falsifiable, after 19 tests:0[-5,0,3,5,7,8]Whew.Generators for Recursive TypesHere is a naive definition of arbitrary lists:instance Arbitrary a => Arbitrary [a] wherearbitrary =oneof [r eturn [],liftM2 ( :) ar bitrary arbitrary]Why is this not what we want?Generators for Recursive TypesHere is a naive definition of arbitrary lists:instance Arbitrary a => Arbitrary [a] wherearbitrary =oneof [r eturn [],liftM2 ( :) ar bitrary arbitrary]Why is this not what we want?Better:instance Arbitrary a => Arbitrary [a] wherearbitrary =frequency [( 1, re turn []),(7, liftM2 (:) arbitrary arbitrary)]Generators for TreesHowever, in some cases