Description
Problem 1. (5 points) Put your full name, UIN, and acknowledgements of any help received
in the head comment in your .hs file for this assignment.
Problem 2. (10 points) Chapter 8, Exercise 1. (The function definition for mult is given
in appendix A.) Carefully study the recursive type of natural numbers in Section 8.4. Using
the definitions of the recursive data type Nat, mult and add, show how 2 × 2 = 4 proceeds,
in the same way as showing how 2 + 1 = 3 proceeds given in Section 8.4 (page 97).
Problem 3. (25 points) [Make sure you read Chapter 16 before attempting this problem.]
Chapter 16. Exercise 6, page 247. This problem has two parts. Given the following data
type
data Tree = Leaf Int | Node Tree Tree
1. (5+5 = 10) Given a tree, function leaves counts the number of leaves in the tree, and
function nodes the number of internal nodes in the tree. Define leaves and nodes.
The function types are as follows.
leaves :: Tree -> Int
nodes :: Tree -> Int
2. (Base case 5 points + inductive case 10 points) Prove the following property by induction on trees.
leaves t = nodes t + 1
Problem 4. (60 points) Chapter 8, Exercise 9. Study Section 8.7 carefully before attempting this problem.
Have fun!
2
