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.
Good luck!
0 (*). Expression and Integer Trees
Expressions
From Thompson's book, read Chapter 14, sections 14.2 to 14.4.
Alternatively, you can take a look at the datatype Expr for
expressions with variables from the
lecture: ExprVar.hs.
Among other things, the book introduces a datatype Expr
data Expr = Lit Int
| Add Expr Expr
| Sub Expr Expr
which is similar to the type I used in the lecture.
Given an expression we want to evaluate it. This is done
using eval
defined by
eval :: Expr -> Int
eval (Lit n) = n
eval (Add e1 e2) = eval e1 + eval e2
eval (Sub e1 e2) = eval e1 - eval e2
We also want be able to show an expression
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
size :: Expr -> Int
which counts the number of operators in an expression.
C(*). Add the operations of multiplication and integer
division to the type Expr
, and redefine the
functions eval
,showExpr
, and size
to
include the new cases. What does your eval
do when you
divide by zero? Write one version of eval
with the result
type Maybe Int
.
D. Instead of adding extra constructors to the Expr
datatype as in C it is possible to factor the definitions
data Expr = Lit Int
| Op Ops Expr Expr
data Ops = Add | Sub | Mul | Div
Show how the functions eval
, showExpr
,
and size
are defined for this type. How would you add yet
another extra operation Mod
for remainder on integer
division?
E. 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
(using deriving Show
)
it appears in prefix
form as 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.,
redefine Expr
as
data Expr = Lit Int
| Expr :+: Expr
| Expr :-: Expr
Redefine the above functions using this datatype with infix constructors.
Integer Trees
A 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 NTree
by
data NTree = NilT
| Node Int NTree NTree
We can sum the nodes and calculate the depths of a tree as follows
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 NTree
.
C(*). Define a function to decide whether a number is an
element of an NTree
.
D. Define functions to find the maximum and minimum values
held in an NTree
.
E(*). A tree is reflected by swapping left and right
sub-trees, recursively. Define a function to reflect
an 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
collapse, sort :: NTree -> [Int]
which turn a tree into a list. The function collapse
should
enumerate the left sub-tree, then the value at the node and finally
the right sub-tree; sort
should sort the elements in
ascending order. For example,
collapse (Node 3 (Node 4 NilT NilT) NilT) = [4,3]
sort (Node 3 (Node 4 NilT NilT) NilT) = [3,4]
Write a suitable QuickCheck property for your functions!
1 (*). File Systems
A 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.
A. Design a data type to represent the
contents of a directory. Ignore the contents of files: you are
just trying to represent file names and the way they are
organised into directories here.
B. Define a function to search for a given file name in a
directory. You should return a path leading to a file with the
given name. Thus if your directory contains a, b, and c, and b is
a directory containing x and y, then searching for x should
produce b/x.
2. Exercises on Propositional Logic
A 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.
A. Design a data type Prop
to 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,
[("p",True),("q",False)]
.
Define a function
truthValue :: Prop -> [(String,Bool)] -> Bool
which determines whether the proposition is true when the
variables have the values given.
C. Define a function
tautology :: Prop -> Bool
which returns True
if the proposition holds for all values of
the variables appearing in it.
Congratulations! You have implemented a simple theorem prover.
3 (*). Exercises on type Expr from the Lecture
Take a look at the datatype Expr
for expressions with variables
from the lecture: ExprVar.hs.
In the lecture, I showed a function for differentiating expressions, called
diff
(Swedish: "derivera").
diff :: Expr -> Name -> Expr
diff (Num n) x = Num 0
diff (Add a b) x = Add (diff a x) (diff b x)
diff (Mul a b) x = Add (Mul a (diff b x)) (Mul b (diff a x))
diff (Var y) x
| x == y = Num 1
| otherwise = Num 0
A.
Define a property that checks that, for each expression e, the derivative of e
to x does not contain more variables than e.
Does the opposite hold also?
The result of the diff
function often contains expressions that
can be simplified considerably.
B.(*) Define a function simplify that, given an expression e,
creates an expression that is equivalent to e, but simplified. Examples of
simplifications you could do are:
- 2+3 --> 5
- 2*x+6+5*x+6 --> 7*x+12
- 0*x+-2+5*y+3 --> 5*y+1
You can decide yourself how ambitious you want to be!
We have made a small start for you in the file
ExprVar.hs
Hint: This exercise is more open-ended.
You can try to define simplify recursively. You will however
notice that it is difficult to accomplish many simplifications. Take a look at
the function assoc in chapter 14 in Thompson's book:
assoc :: Expr -> Expr
assoc (Add (Add e1 e2) e3) = assoc (Add e1 (Add e2 e3))
assoc (Add e1 e2) = Add (assoc e1) (assoc e2)
assoc (Sub e1 e2) = Sub (assoc e1) (assoc e2)
assoc (Lit n) = Lit n
(A different, but more ambitious, approach is to design a new type, that
represents a normal form for expressions, for example
polynomials. Your simplify
function could simply transform an
expression into a polynomial, and back into expressions again. How would you
model polynomials over multiple variables as a type in Haskell?)
Make sure that the following property holds for your simplify
function:
for each expression e, evaluating it in an environment generates the
same result before and after simplifying:
prop_SimplifyCorrect :: Expr -> Env -> Property
prop_SimplifyCorrect e (Env env) =
eval env e === eval env (simplify e)
C. Define a property:
prop_SimplifyNoJunk :: Expr -> Bool
that checks that the result of simplification does not "leave any junk". In
other words, the result of simplification should for example not have
subexpressions of the form:
- Add (Num n) (Num m)
- Mul (Num 0) b
- Add a a
And so forth. What is allowed as "junk" and what is not of course depends on
your simplification function, and what you expect from it.
This property boils down to defining a function
noJunk:: Expr -> Bool
.
We have already made a small start for you in
ExprVar.hs.
D. Define a property:
prop_SimplifyDiff :: Expr -> Bool
that checks that differentiating an expression and then simplifying it should
have the same result as simplifying it first, then deriving, and then
simplifying.
Do you expect it to hold?
Does it actually hold for your simplification function?