...
| Code Block |
|---|
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)...
}
}
|
...
| Code Block |
|---|
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
}
}
|
...
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!!
Exercises:
- Add method to your lists classes that will calculate the product of all the elements.
- Add a method to return a copy of your list.
- Add a method to return all the positve values in the list.
- Add methods to return the largest/smallest element of the list.
Integer.MAX_VALUEandInteger.MIN_VALUEare static fields of theIntegerclass 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.
...
| Code Block |
|---|
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) {
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
...
- Write a method called
prodNumsthat returns the product of the number in the list, using a tail recursive helper method. - Revise the preceding definition to terminate immediately if it encounters a 0 in the list of numbers being multiplied.
- Write a method called
makePalindromethat 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 thelist (1, 2, 3, 2, 1). - Write a method called
reversethat reverses the list using a tail-recursive helper. - Come up with another version of
listString. Call itlistString2. How many different ways of writing this method can you come up with? Are some tail recursive and some not?