Exercises for Week 5: Recursive Datatypes
Here are some exercises designed to help you practice programming with recursive datatypes.
If you do not have time to do all these exercises, don't worry. The exercises are intended to provide enough work to keep the most experienced students busy. If you do all exercises marked with an (*) you have probably understood this week's material.
0 (*). Expression and Integer Trees
Consider the datatype
which is similar to the type used in the lecture. Given an expression we want to evaluate it. This is done usingdata Expr = Lit Int | Add Expr Expr | Sub Expr Expr
We also want be able to show an expression:eval :: Expr -> Int eval (Lit n) = n eval (Add e1 e2) = eval e1 + eval e2 eval (Sub e1 e2) = eval e1 - eval e2
showExpr :: Expr -> String showExpr (Lit n) = show n showExpr (Add e1 e2) = "(" ++ showExpr e1 ++ "+" ++ showExpr e2 ++")" showExpr (Sub e1 e2) = "(" ++ showExpr e1 ++ "-" ++ showExpr e2 ++")"
A. Give calculations of
eval (Lit 67) eval (Add (Sub (Lit 3) (Lit 1)) (Lit 3)) showExpr (Add (Lit 67) (Lit (-34)))
B(*). Define the function
which counts the number of operators in an expression.size :: Expr -> Int
C(*). Add the operations of multiplication and integer
division to the type
Expr, and redefine the
include the new cases. What does your
eval do when you
divide by zero? Write one version of
eval with the result
Maybe Int. (You return Nothing when division by 0 occurs somewhere in the expression.)
D. Instead of adding extra constructors to the
datatype as in C it is possible to factor the definitions
Show how the functionsdata Expr = Lit Int | Op Ops Expr Expr data Ops = Add | Sub | Mul | Div
sizeare defined for this type. How would you add yet another extra operation
Modfor remainder on integer division?
In Haskell back-quotes allow us to use constructors in infix form
(indeed any function) like in
(Lit 3) `Add` (Lit 15).
However, if this expression is shown
it appears in prefix
Add (Lit 3) (Lit 15).
It is also possible to use infix operators for constructor names where
the first character must be a
':'. We can, e.g.,
data Expr = Lit Int | Expr :+: Expr | Expr :-: ExprRedefine the above functions using this datatype with infix constructors.
Integer TreesA tree of integers is either nil or given by combining a value and two sub-trees. In Haskell we can introduce the datatype of integer trees
We can sum the nodes and calculate the depths of a tree as followsdata NTree = NilT | Node Int NTree NTree
sumTree :: NTree -> Int sumTree NilT = 0 sumTree (Node n t1 t2) = n + sumTree t1 + sumTree t2 depth :: NTree -> Int depth NilT = 0 depth (Node n t1 t2) = 1 + max (depth t1) (depth t2)
A. Give a calculation of
sumTree (Node 3 (Node 4 NilT NilT) NilT) depth (Node 3 (Node 4 NilT NilT) NilT)
B(*). Define functions to return the left- and right-hand
sub-trees of an
C(*). Define a function to decide whether a number is an
element of an
D. Define functions to find the maximum and minimum values
held in an
E(*). A tree is reflected by swapping left and right
sub-trees, recursively. Define a function to reflect
NTree. What is the result of reflecting twice? Write a
QuickCheck property for that!
(In order to be able to test your properties, you have to make NTree an instance of Arbitrary.)
F. Define functions
which turn a tree into a list. The functioncollapse, sort :: NTree -> [Int]
collapseshould enumerate the left sub-tree, then the value at the node and finally the right sub-tree;
sortshould sort the elements in ascending order. For example,
Write a suitable QuickCheck property for your functions!collapse (Node 3 (Node 4 NilT NilT) NilT) = [4,3] sort (Node 3 (Node 4 NilT NilT) NilT) = [3,4]
1 (*). File SystemsA file either contains data or is a directory. A directory contains other files (which may themselves be directories) along with a name for each one.
2. Exercises on Propositional LogicA proposition is a boolean formula of one of the following forms:
- a variable name (a string)
- p & q (and)
- p | q (or)
- ~p (not)
where p and q are propositions. For example, p | ~p is a proposition.
Propto represent propositions.
B. Define a function
vars :: Prop -> [String]
which returns a list of the variables in a proposition. Make sure each variable appears only once in the list you return.
Suppose you are given a list of variable names and their
values, of type Bool, for example,
Define a function
which determines whether the proposition is true when the variables have the values given.truthValue :: Prop -> [(String,Bool)] -> Bool
C. Define a function
tautology :: Prop -> Bool
True if the proposition holds for all values of
the variables appearing in it.
Congratulations! You have implemented a simple theorem prover.
5. Approximating 0-solutions of functionsDefine a function:
The idea is that solve f (x0,x1) finds a value x in between x0 and x1 such that f x == 0.0.solve0 :: (Double -> Double) -> (Double,Double) -> Double
If needed, you may assume the following reasonable assumptions:
solve0 (+1) (-3,3)-1.0
solve0 cos (2,5)4.71238898031879
solve0 (\x -> x ^ 2 - 10) (1,10)3.16227766017255
solve0 (\x -> x ^ 3) (1,1)*** Exception: no solution!
- f is continuous
- f x0 ≤ 0 ≤ f x1
Main> solve0 (\x -> x ^ 2) (1,10) Program error: bad interval!Your program has to approximate this value. For example, the answer to the first example above might be -0.999999999941792 instead of -1.0, and that is OK.
One way to do this is to use the "halving" method: Calculate x that lies somewhere in between x0 and x1. Investigate f x. Then recursively solve f on either the interval (x0,x) or (x,x1).
There are other methods too!