Comp 212 Homework 1
Java Finger Exercises

Due 99.Sept.13 10:00 AM.

Before doing these exercises, you should skim Ch. 1, and read Ch. 2.1-2.8 and 3.1 of JPL (The Java Programming Language). You should also consult JPL for Java terminologies that you do not understand. The first tutorial will acquaint you with the process of preparing and compiling Java programs using emacs.

Functional List

• new Empty() forms an empty list;
• new Cons(a,d) forms a list consisting of the int a followed by the list d;
• l.car() returns the first int in the list object l;
• l.cdr() returns the tail (all but the first element) of the list object l; and
• l.toString() returns a String description of the list object l. This String can be printed with System.out.println.

Problems

1. Add the method int sum() to class FunList and all of its concrete variants. Calling l.sum() returns the sum of all the numbers in the list l.
2. For FunList and its concrete variants, write the method int max(), which returns the maximum element of a Cons object only. On Empty lists, max() should return an NoSuchElementException.
3. For FunList and its concrete variants, write the method dup(), which returns a new list with the first element duplicated.¹ That is, if l1 were the list (4, 5, 6), then l1.dup() would be the list (4, 4, 5, 6). Decide what Empty.dup() should return, and explain your design decision. In your test cases, include a test of dup on a variable which is declared to be of class FunList. Does your function max() still work fine on lists returned by dup()?
4. Use FunList as an example to design and imlement FunBiTree (functional binary tree) defined as follows:
   • new Empty() is an empty FunBiTree;
   • new NEBiTree(l, v, r) is a FunBiTree consisting of an Integer v (called the root object), a FunBiTree l (called left subtree), and a FunBiTree r (called right subtree). Note that r is an Integer object, and not an int;
   • t.root() returns the root Integer object in the tree object t;
   • t.left() and t.right() returns the left subtree and the right subtree, respectively, of the tree object t; and
   • t.toString() returns a String description of the tree object t.
   In standard Java programming practice, each class is saved in a file whose name is the same as the class name itself. However, for the sake of simplicity, save FunBiTree and its variants in a file named FunBiTree.java as done in FunList.java.
5. Add the method Integer sum() to class FunBiTree and all of its concrete variants. Calling t.sum() returns the Integer sum of all the numbers in the tree t.
6. For FunBiTree and its concrete variants, write the method Integer max(), which returns the Integer maximum element of a NEBiTree object only. On Empty trees, max() should return an NoSuchElementException.
7. For FunBiTree and its concrete variants, write the method Boolean isEmpty(), which returns the Boolean representing false if the tree is not empty, and the Boolean representing true if the tree is empty. There are at least two ways to write this function. Write them both. Name one Boolean isEmpty1() and the other Boolean isEmpty2(). Boolean isEmpty1() should make use of the operator instanceof.
8. A FunBiTree is said to be a leaf if it is not empty and its left and right subtrees are empty. For FunBiTree and its concrete variants, write the method Boolean isLeaf(), the Boolean representing true if the tree is a leaf, and the Boolean representing false otherwise. Is there a way to write this method without writing a conditional to check (directly/indrectly) the subtrees for emptyness? If no, explain your answer. If yes, write the function and name it Boolean isLeaf2(); of course, feel free to write additional helper functions, as long as these do not directly/indirectly check for emptyness with a conditional.

As with all programs in this course, lack of good coding style (good style includes reasonable variable names, a header before each non-overridden function, reasonable indentation²) will result in a substantial loss of points (see Comp 212 Course Guide). All programs in this exercise should be written in a purely functional style: no object fields should be modified once they have been initialized by a constructor.

In class on Monday, September 13, turn in

• a separate hardcopy for each of the solutions to the above problems together with the output of your test cases; make sure your name appear on each of the hardcopies so that your grade can be properly recorded,
• printed (or hand-drawn) UML diagrams of all your class designs.

² Remember emacs's M-x indent-region command. (back)