Little Java Exerices 1
Practice the Composite and Interpreter Patterns

Before doing these exercises, you should read the classnotes. through Section 1.7.

Classes

• new Empty() forms an empty list;
• new Cons(a,d) forms a list consisting of the int a followed by the list d;
• l.getFirst() returns the first int in the Cons object l;
• l.getRest) 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.

Similarly, the file ~comp212/hw/01/Tree.java contains the definition of a Tree class. Each object of type Tree represents either a leaf containing an int or a branch containing two subtrees. The class definition for Tree supports three important operations:

• new Leaf(n) forms a leaf containing the int n,
• new Branch(l,r) forms a branch consisting of the subtrees l and r, and
• t.toString() which constructs a string description for the tree t.

Problems

1. Add the method int sum() to class IntList. Calling s.sum() returns the sum of all the numbers in s.
2. Add the method int sum() to the class Tree.
3. Add the methods int size() to the class Tree. For example, the Tree

              /\
             /\ 13
            7 /\ 
             9  11
   

   has size is seven: four leaves, three branches. (It requires seven new statements to build this Tree.)

   A small amount of extra credit: How can you build a tree with this same shape (but possibly different numbers) using four new statements? Fewer? Note that the size of any such trees is still seven.

4. Going back to the file IntList.java, write the method int max(), which returns the maximum element of a Cons object only. On Emptys, max() should return an IllegalArgumentException.
5. Write the Cons 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). In your test cases, include a test of dup on a variable which is declared to be of class IntList. (You will need to do a cast.) Does your function max() still work fine on lists returned by dup()?

Good coding style is important. Good style includes reasonable variable names, a purpose statement in a comment before each non-overridden function, and reasonable indentation²) 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.

² Remember that DrJava can indent entire programs. Select the entire program with the mouse and hit the TAB key. (back)