Below, the exercise problems are from the Haskell Textbook: \Programming in Haskell, 2nd Ed.", by Graham Hutton. Some problems are modi ed (with additional requirements) by the instructor. Please read corresponding textbook chapters and the problem statements carefully, paying attention to the requirements. There may be signi cant penalties for not ful lling such requirements.
Keep the name and type of each function exactly the same as given in the problem statement and the skeleton code. Also, do not remove or modify the test list or the main function. If you remove or modify those, then you will be penalized for that.
Problem 1. (5 points) Put your full name, UIN, and acknowledgements of any help received in the head comment in your .hs le for this assignment.
Problem 2. (10 points) Chapter 8, Exercise 1. (The function de nition for mult is given in appendix A.) Carefully study the recursive type of natural numbers in Section 8.4. Using the de nitions 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. De ne 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 in-duction on trees.
leaves t = nodes t + 1
Problem 4. (60 points) Chapter 8, Exercise 9. Study Section 8.7 carefully before attempt-ing this problem.
Have fun!
2
