## 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

Consider the datatype

,
**Expr**

which is similar to the type used in the lecture. Given an expression we want to evaluate it. This is done usingdataExpr=LitInt|AddExprExpr|SubExprExpr

`eval`

defined by
We also want be able to show an expression:eval::Expr->Inteval(Litn)=neval(Adde1e2)=evale1+evale2eval(Sube1e2)=evale1-evale2

showExpr::Expr->StringshowExpr(Litn)=shownshowExpr(Adde1e2)="("++showExpre1++"+"++showExpre2++")"showExpr(Sube1e2)="("++showExpre1++"-"++showExpre2++")"

**A.** Give calculations of

eval(Lit67)eval(Add(Sub(Lit3) (Lit1)) (Lit3))showExpr(Add(Lit67) (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
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

. (You return Nothing when division by 0 occurs somewhere in the expression.)
**Maybe** **Int**

**D.** Instead of adding extra constructors to the `Expr`

datatype as in **C** it is possible to factor the definitions

Show how the functionsdataExpr=LitInt|OpOpsExprExprdataOps=Add|Sub|Mul|Div

`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 `(`

.
However, if this expression is shown
(using **Lit** 3) `**Add**` (**Lit** 15)

)
it appears in prefix
form as **deriving** **Show**

.
**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 :-: ExprRedefine 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
We can sum the nodes and calculate the depths of a tree as followsdataNTree=NilT|NodeIntNTreeNTree

sumTree::NTree->IntsumTreeNilT=0sumTree(Nodent1t2)=n+sumTreet1+sumTreet2depth::NTree->IntdepthNilT=0depth(Nodent1t2)=1+max(deptht1) (deptht2)

**A.** Give a calculation of

sumTree(Node3 (Node4NilTNilT)NilT)depth(Node3 (Node4NilTNilT)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

which turn a tree into a list. The functioncollapse,sort::NTree->[Int]

`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,
Write a suitable QuickCheck property for your functions!collapse(Node3 (Node4NilTNilT)NilT)=[4,3]sort(Node3 (Node4NilTNilT)NilT)=[3,4]

### 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.

**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

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

which returns `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 functions

Define a function:The idea is thatsolve0::(Double->Double)->(Double,Double)->Double

**solve f (x0,x1)**finds a value x in between x0 and x1 such that f x == 0.0.

Examples:

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

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.Main>solve0 (\x -> x ^ 2) (1,10) Program error: bad interval!

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!