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!

From the book, read Chapter 14, sections 14.2 to 14.4.

Among other things, a datatype **Expr** is introduced there, which is similar
to the type I used in the lecture.

Now, do the following exercises: **14.15, 14.16(*), 14.17(*), 14.18, 14.20**.

In exercise **14.17**, implement one version of **eval** with the result
type Maybe Int.

**Integer Trees**

From the book, read Chapter 14, sections 14.2 to 14.4.

Among other things, a datatype **NTree** is introduced there, which
represents *trees of integers*.

Now, do the following exercises: **14.19, 14.21(*), 14.22(*), 14.23, 14.24(*),
14.25**.

Write suitable QuickCheck properties for the functions **reflect**,
**collapse**, and **sort**.

(In order to be able to test your properties, you have to
make **NTree** an instance of Arbitrary.)

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

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

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: "derivat").

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
enormously simplified.

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

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 the book.

(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 e (Env env) = eval env e == eval env (simplify e)

**C.** Define a property:

prop_SimplifyNoJunk :: Expr -> Boolthat 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: 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 -> Boolthat 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?