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)...
    }

}

Let's take a look at what this means in light of what we'v learned from Scheme... 

From Scheme To Java

Has the world really changed as we transition from Scheme to Java?  Well, yes and no.   Yes, because we now look at the world as a collection of objects rather than as a collection of funcitons.   No, because CS principles still hold and so the same concepts must be still hold true no matter what language we express them in.

...

• The template is a statement of an invariant properties of lists and the functions that process them.   That is, the template tells us things that are true for all lists.
• A function on a list is fundamentally separable into two parts, differentiated by the cond statement:
  • The base case: The empty list is processed separately from the non-empty list.
  • The inductive case: The non-empty list (cons) is processed separately from the empty list and involves the two pieces of the non-empty list, namely first and rest.
• A recursive algorithm involves processing the rest of the list.

...

 The biggest change that we will see when we switch to Java is due to the fact that objects "know" who they are and that we will use delegation to take advantage of that fact.   Thus, the " cond " statement in the Scheme function, whose sole purpose is to diffrentiate between the base and inductive cases, is no longer needed!   Instead, we will make the sum function a part of the list, and simply ask the list to sum itself.   Since any list object already knows whether it is empty or non-empty, it does not need to have a conditional for that purpose--the question is already answered and thus does not need to be asked!

...

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

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?  

Remember that the sole function of the cond statement was to differentiate between the base and inductive cases.  What we did was to move that differentiation from a functional, operational process to a structural, architectural implementation.  The base and inductive cases are differentiated not at run-time, but at design-time, when we define the EmptyIntList and ConsIntList sub-classes of IntList.   The differentiation is not a process that is executed but a fundamental relationship between the classes in our system.

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.

...

1. Write another version of listString that is tail recursive. Call it listString2 . (Can you think of a non-tail recursive version?)
2. Write a method called prodNums that returns the product of the number in the list, using a tail recursive helper method.
3. Revise the preceding definition to terminate immediately if it encounters a 0 in the list of numbers being multiplied.
4. 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) .
5. Write a method called reverse that reverses the list using a tail-recursive helper.

Access Permissions: (Please don't edit)

...

1. .

...