12/08/2020 Code (Week 3 Video)
Code (Week 3 Video) Basic QuickCheck
import Test.QuickCheck
import Data.Char
import Data.List
—
Testable
Arbitrary Testable
—
—
prop_reverseApp :: [Int] -> ([Int] -> Bool)
prop_reverseApp xs ys =
reverse (xs ++ ys) == reverse ys ++ reverse xs
divisible :: Int -> Int -> Bool
divisible x y = x `mod` y == 0
prop_refl :: Positive Int -> Bool
prop_refl (Positive x) = divisible x x
prop_unwordsWords s = unwords (words s) == s
prop_wordsUnwords l = all (\w -> all (not . isSpace) w && w /= []) l
==> words (unwords l) == l
Arbitrary Testable
Merge Sort Example
split :: [a] -> ([a],[a])
split [] = ([],[])
split [a] = ([a],[])
split (x:y:xs) = let (l,r) = split xs
in (x:l,y:r)
prop_splitPerm xs = let (l,r) = split (xs :: [Int])
in permutation xs (l ++ r)
permutation :: (Ord a) => [a] -> [a] -> Bool
www.cse.unsw.edu.au/~cs3141/20T2/Week 03/1Vid/Code.html
1/3
12/08/2020 Code (Week 3 Video)
Lazy Evaluation
permutation xs ys = sort xs == sort ys
permutation’ :: (Eq a) => [a] -> [a] -> (a -> Bool)
permutation’ xs ys = \x -> count x xs == count x ys
where
count x l = length (filter (== x) l)
merge :: (Ord a) => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) | x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
prop_mergePerm xs ys = permutation (xs ++ (ys :: [Int] )) (merge xs ys)
prop_mergeSorted (Ordered xs) (Ordered ys) = sorted (merge (xs :: [Int]) ys)
sorted :: Ord a => [a] -> Bool
sorted [] = True
sorted [x] = True
sorted (x:y:xs) = x <= y && sorted (y:xs)
mergeSort :: (Ord a) => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = let (l,r) = split xs
in merge (mergeSort l) (mergeSort r)
prop_mergeSortSorts xs = sorted (mergeSort (xs :: [Int]))
prop_mergeSortPerm xs = permutation xs (mergeSort (xs :: [Int]))
prop_mergeSortExtra xs = mergeSort (xs :: [Int]) == sort xs
prop_mergeSortUnit = mergeSort [3,2,1] == [1,2,3]
main = do
quickCheck prop_mergeSortUnit
quickCheck prop_mergeSortSorts
quickCheck prop_mergeSortPerm
www.cse.unsw.edu.au/~cs3141/20T2/Week 03/1Vid/Code.html
2/3
12/08/2020 Code (Week 3 Video)
{-# LANGUAGE BangPatterns #-} sumTo’ !a 0 = a
sumTo’ !a n = sumTo’ (a+n) (n-1)
— sumTo’ 0 5
— sumTo’ (0+5) (5-1)
— sumTo’ (0+5) 4
— sumTo’ (0+5+4) (4-1) — sumTo’ (0+5+4) 3
— sumTo’ (0+5+4+3) (3-1) — sumTo’ (0+5+4+3) 2
— ..
— sumTo’ 0 100000
— sumTo’ (0 + 100000 + 99999 + 99998 + 99997 + ….) 0 —
sumTo :: Integer -> Integer
sumTo 0 = 0
sumTo n = sumTo (n-1) + n
www.cse.unsw.edu.au/~cs3141/20T2/Week 03/1Vid/Code.html
3/3