Page History

...

abstract class IntList {
    abstract returnType methodName(parameter_list); // returnType may be Void
}

class EmptyIntList extends IntList {
    static EmptyIntList ONLY = new EmptyIntList(); // Singleton
    private EmptyIntList() {}
 
    returnType methodName(parameter_list) {
        // base case code
    }
}

class ConsIntList extends IntList {
    int first;
    IntList rest;
    returnType methodName(parameter_list) {
        // ... first ...
        // ... rest.methodName(parameter_list)...
    }

}

...

abstract class IntList {
    abstract int sum(); // all IntLists know how to sum themselves!
}

class EmptyIntList extends IntList {
    static EmptyIntList ONLY = new EmptyIntList(); // Singleton
    private EmptyIntList() {}
 
   /**
    * The sum of an empty list
    * @return zero always
    */
    int sum() {
        return 0; // base case code
    }
}

class ConsIntList extends IntList {
    int first;
    IntList rest;

   /**
    * The sum of a non-empty list
    * @return first plus the sum of rest
    */
    int sum() {
        return first + rest.sum()  ; // inductive case code
    }
}

 Notice that, to within syntactical differences, the bodies of the base and inductive cases are identical between Scheme and Java implementations?

Why don't we need to know the exact type of rest?

Where Did The cond Go? 

 The Java implemenation enables us to clearly focus on and differentiate between the base and inductive cases by separating them into different sub-classes.  But where, you might ask, did the cond statement in the Scheme implementation go into the Java implementation?  

...

This should not be surprising in that the cond statement was part of the invariant function template for all lists.    This tells us that differentiation between base and inductive cases is fundamental to the nature of lists.    Scheme is unable to express this fact in its structural representations of data, i.e. structs, so we were forced to represent it in terms of an invariant function template.    Java, however, has the ability to express this relationship in terms of its inheritance hierarchy and thus we use delegation to leverage this "polymorphic" behavior of the IntList sub-classes to let them differentiate themselves.

NO COND!!

More List Exercises

A Scheme-like String representation of lists.

 Exercises:

1. Add method to your lists classes that will calculate the product of all the elements.
2. Add a method to return a copy of your list.
3. Add a method to return all the positve values in the list. 
4. Add methods to return the largest/smallest element of the list.  
   • Integer.MAX_VALUE and Integer.MIN_VALUE are static fields of the Integer class that will give you the largest and smallest possible integer values in Java.
   • For simplicity's sake, just return the appropriate value above in the situation where no min or max value exists in the list.   We will learn how to throw exceptions later.

More List Exercises

A Scheme-like String representation of lists.

Suppose we want to display an empty list as () and the list Suppose we want to display an empty list as () and the list containing 1, 2, 3 as (1, 2, 3) . How do we do this? We need to add a method to the InList hierarchy of classes to perform this computation. Let's call this method listString() and let's proceed together.

Step 1: Instantiate the interpreter code template given above by replacing returnType with String , the methodName with listString and the parameter_list with nothing. Be sure to create one file for each class. The code will not compile. Why?

Step 1.5: Add syntactically correct code to the template so that the whole thing compile.

Step 2: Write appropriate JUnit test classes. Because of lack of time, we will not do this step in class.

Step 3: Write the code for listString in EmptyInstList . This is trivial! Make sure it passes the JUnit test though!

Step 4: Write the code for listString in ConsIntList . You can try the structural recursive code given in the template and see that it will not work. This is because by the time you reach the end of the list (i.e. when rest is the empty list), you need to do something different from what EmptyIntList . listString() is programmed to do. You will need to call on rest to perform an auxiliary ("helper") method to get the job done. Let's call this helper method listStringHelp .

...

The code will not compile because we have yet to add the method listStringHelp to the IntList hierarchy.

Step 5: Add the method String listStringHelp(String acc) to the IntList hierarchy; add stub template code so that the whole thing compile. Unless you accidentally write the correct code, the JUnit test for ConsIntList will not pass still.

Step 6: Write JUnit test code for listStringHelp . Again, due to lack of time, we will not do that here in the lab. Actually, more than often, writing the test code will help write the code for the method in question.

Step 7: Write the code for EmptyIntList.listStringHelp(String acc) What should the empty do here? It knows it has the accumulated string representation of the whole list so far and that all it needs is the closing parenthesis. So all it has to do is to add the closing parenthesis to the accumulated string and return: return acc + ")"; (And make sure it passes the JUnit test).

Step 8: Write the code for ConsIntList.listStringHelp (and make sure that it passes the JUnit test). What can a non-empty list do here? All it needs to do is to concatenate a comma and its first to the accumulated string representation so far and pass it on to rest to complete the job: return rest.listStringHelp(acc + ", " + first); (And make sure it passes the JUnit test).

...

abstract class IntList {
    /** Computes a String representation of this list wiht matching parentheses
      * as in Scheme.  For example, the list containing 1, 2 and 3 should return
      * (1, 2, 3) and the empty list should return ().
      * @return a non empty String consisting of elements in this list enclosed
      * in a pair of matching parenthesis, separated by commas.
      */
    abstract String listString();

    /** Accumulator helper method for listString to compute the String
      * required representation of this list given the accumulated
      * String representation of the preceding list.
      * @param acc the accumulated String representation of the list that
      * precedes this list.
      * @return a non empty String consisting of elements in this list enclosed
      * in a pair of matching parenthesis, separated by commas.
      */
    abstract String listStringHelp(String acc);
}


class EmptyIntList extends IntList {

    /** @return "()"*/
    String listString() { return "()"; }
    /** @param acc the accumulated String representation of the list that
      * precedes this list.  For example "(5, 3"
      * @return a non empty String consisting of elements in this list enclosed
      * in a pair of matching parenthesis, separated by commas.  For example,
      * "(5, 3)"
      */
    String listStringHelp(String acc) {
        return acc + ")";
    }
}

class ConsIntList extends IntList {
    int first;
    IntList rest;

    /** Calls on rest to perform the helper method listStringHelp passing it
      *   the accumulated String representation so far, which is "(" + first.
      * @return a non empty String consisting of elements in this list enclosed
      *    in a pair of matching parenthesis, separated by commas.
      */
    String listString() {
        return rest.listStringHelp("(" + first);
    }

    /** @param acc the accumulated String representation of the list that
      *   precedes this.  For example "(5, 3"
      * @return a non empty String consisting of elements in this list enclosed
      *   in a pair of matching parenthesis, separated by commas.  For example,
      *   "(5, 3)"
      */
    String listStringHelp(String acc) { listStringHelp(String acc) {
        return rest.listStringHelp(acc + ", " + first);
    }
}

/** Testing empty lists. */
class TestEmptyIntList extends TestCase {

    void test_listString() {
        EmptyIntList mt = new EmptyIntList();
        assertEquals(mt + ".listString()", "()", mt.listString());
    }
}

Lab Exercises

...

1. Write a method called prodNums that returns the product of the number in the list, using a tail recursive helper method.
2. Revise the preceding definition to terminate immediately if it encounters a 0 in the list of numbers being multiplied.
3. Write a method called makePalindrome that returns a list consisting of the input list and its mirror around the last element, using a (non tail-recursive) helper with an accumulator. For example, (1, 2, 3).makePalindrome () returns the list (1, 2, 3, 2, 1) .
4. Write a method called reverse that reverses the list using a tail-recursive helper.
5. Come up with another version of listString. Call it listString2.  How many different ways of writing this method can you come up with?   Are some tail recursive and some not?