12/08/2020 Exercise (Week 4)
Exercise (Week 4)
DUE: Wednesday 1 July 15:00:00 Getting Started
CSE
Stack
Download the exercise tarball and extract it to a directory on your local machine. This tarball contains a le, called Ex03.hs , wherein you will do all of your programming.
To test your code, run the following shell commands to open a GHCi session:
$ stack repl
Configuring GHCi with the following packages: Ex03
Using main module: 1. Package ‘Ex03’ component exe:Ex03 …
GHCi, version 8.2.2: http://www.haskell.org/ghc/ 😕 for help
[1 of 1] Compiling Ex03 (Ex03.hs, interpreted)
Ok, one module loaded.
*Ex03> quickCheck prop_mysteryPred_1
…
Calling quickCheck in the above way will run the given QuickCheck property with 100 random test cases.
Note that you will only need to submit Ex03.hs , so only make changes to that le.
QuickCheck and Search Trees
www.cse.unsw.edu.au/~cs3141/20T2/Week 04/exercise.html
1/5
12/08/2020 Exercise (Week 4)
The le includes the support code described in the following as well as stubs for the three functions that you must implement. The QuickCheck properties discussed below are also included.
We include a binary tree implementation, plus a predicate, isBST , which returns True if a tree is a binary search tree (that is, an in x traversal of the tree is sorted).
This is a data invariant for our BST operations.
data BinaryTree = Branch Integer BinaryTree BinaryTree
| Leaf
deriving (Show, Ord, Eq)
isBST :: BinaryTree -> Bool
isBST Leaf = True
isBST (Branch v l r) = and [ allTree (< v) l, allTree (>= v) r
, isBST l, isBST r ]
where allTree :: (Integer -> Bool) -> BinaryTree -> Bool
allTree f (Branch v l r) = f v && allTree f l && allTree f r
allTree f (Leaf) = True
We also include insert and deleteAll functions for binary search trees:
— Add an integer to a BinaryTree, preserving BST property. insert :: Integer -> BinaryTree -> BinaryTree
— Remove all instances of an integer in a binary tree, — preserving BST property
deleteAll :: Integer -> BinaryTree -> BinaryTree
An arbitrary generator that generates binary search trees:
If we wanted to check that our generator always generates wellformed inputs, we can check it by running the additional property:
We use the arbitrary search tree generator rather than pre x our properties with a guard like isBST tree ==> to prevent QuickCheck generating lots of spurious test cases.
searchTrees :: Gen BinaryTree
prop_searchTrees = forAll searchTrees isBST
Ex03.hs
www.cse.unsw.edu.au/~cs3141/20T2/Week 04/exercise.html
2/5
12/08/2020 Exercise (Week 4)
mysteryPred
mysteryPred
mysteryPred :: Integer -> BinaryTree -> Bool
prop_mysteryPred_1 integer
= forAll searchTrees $ \tree ->
mysteryPred integer (insert integer tree)
prop_mysteryPred_2 integer
= forAll searchTrees $ \tree ->
not (mysteryPred integer (deleteAll integer tree))
quickCheck
prop_mysteryPred_[1-2]
GHCi
mysterious :: BinaryTree -> [Integer]
prop_mysterious_1 integer
= forAll searchTrees $ \tree ->
mysteryPred integer tree == (integer `elem` mysterious tree)
prop_mysterious_2 = forAll searchTrees $ isSorted . mysterious
isSorted :: [Integer] -> Bool
isSorted (x:y:rest) = x <= y && isSorted (y:rest)
isSorted _ = True
quickCheck
prop_mysterious_[1-2]
www.cse.unsw.edu.au/~cs3141/20T2/Week 04/exercise.html 3/5
insert
deleteAll
Implementing A Mystery Function (Part 1a, 2 Mark)
Write a predicate function , which has the following type signature:
It must satisfy the following QuickCheck properties:
You can test your implementation by simply running in the playground or .
Even more mysterious (Part 1b, 3 Marks)
Write a function mysterious, with the following type signature:
It must satisfy the following QuickCheck properties:
You can test your mysterious implementation by simply running
in a playground or GHCi.
Depending on your exact de nition, this could be an abstraction function for binary search trees. Consider how our binary tree operations like and
12/08/2020 Exercise (Week 4)
could be speci ed using data re nement. Balancing Act (Part 2, 4 Marks)
First, we have the generator:
We use a generator to produce because guarding our properties with etc. means that QuickCheck will waste a lot of time randomly generating lists and checking if they satisfy the guard. We can check if our generator works with the following properties:
Write a function astonishing , of type [Integer] -> BinaryTree that satis es these properties:
sortedListsWithoutDuplicates :: Gen [Integer]
sortedListsWithoutDuplicates
isSorted list ==>
prop_sortedListsWithoutDuplicates_1
= forAll sortedListsWithoutDuplicates isSorted
prop_sortedListsWithoutDuplicates_2
= forAll sortedListsWithoutDuplicates $ \x -> x == nub x
prop_astonishing_1
= forAll sortedListsWithoutDuplicates $ isBST . astonishing
prop_astonishing_2
= forAll sortedListsWithoutDuplicates $ isBalanced . astonishing
prop_astonishing_3
= forAll sortedListsWithoutDuplicates $ \ integers ->
mysterious (astonishing integers) == integers
Where isBalanced is a predicate that returns true if a tree is height-balanced:
isBalanced :: BinaryTree -> Bool
isBalanced Leaf = True
isBalanced (Branch v l r) = and [ abs (height l – height r) <= 1
, isBalanced l
, isBalanced r
]
where height Leaf = 0
height (Branch v l r) = 1 + max (height l) (height r)
www.cse.unsw.edu.au/~cs3141/20T2/Week 04/exercise.html
4/5
12/08/2020 Exercise (Week 4)
Note: This de nition of is a rather generous de nition of balanced trees. Can you nd an example of a tree that is not very balanced for which this function would still return True ? What would a stricter predicate look like?
Submission instructions
You can submit your exercise by typing:
on a CSE terminal, or by using the give web interface. Your le must be named Ex03.hs (case-sensitive!). A dry-run test will partially autotest your solution at
submission time. To get full marks, you will need to perform further testing yourself.
$ give cs3141 Ex03 Ex03.hs
isBalanced
www.cse.unsw.edu.au/~cs3141/20T2/Week 04/exercise.html
5/5