TDA 555
DIT 440
HT 2019

# Introduction to Functional Programming Exercises for Week 6

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

```data Expr = Lit Int
| Sub Expr Expr```
which is similar to the type 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`. (You return Nothing when division by 0 occurs somewhere in the expression.)

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.

### 5. Approximating 0-solutions of functions

Define a function:
`solve0 :: (Double -> Double) -> (Double,Double) -> Double`
The idea is that solve f (x0,x1) finds a value x in between x0 and x1 such that f x == 0.0.

Examples:

```  `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!
```
If needed, you may assume the following reasonable assumptions:
• f is continuous
• f x0 ≤ 0 ≤ f x1
So, you may produce an error when this does not hold:
```  Main> solve0 (\x -> x ^ 2) (1,10)