Rice University - Comp 212 - Intermediate Programming

Spring 2006

Lecture #07 - Using "helper" methods

1. A String Representation for IList

Any IList object is an instance of the class Object and thus inherits the toString() method. This method simply returns the concrete class name, followed by the character '@', following by some hexadecimal code. Such a string representation of a list is not very informative. It is customary to override toString() to provide a custom string representation for a list.

A common string representation of a list displays its contents inside of a pair of matching parentheses in such a way that:

the elements of the list are separated by a space,
there is no space preceding the first element of the list and
no space following the last element of the list.

For example, the string representation of an empty list is "()", while the string representation of a non empty list containing elements 'a', 'b', 'c' in this order is "(a b c)".

To craft an algorithm for toString() to implement the above specification, we first examine a few simple examples and follow the composite design coding pattern, that is when processing a composite, call on each embedded component to process itself.

L is an EmptyList: ().toString() returns "()"; no-brainer here.
L is NEList: We should always think of decomposing the problem into processing _first and _rest (which itself is an IList).
- L contains a single element: (a).toString() returns "(a)". One possible decomposition of this representation is "(" + "a" + the null string + ")", where "a" is the string representation of _first of L. In this case, _rest is an EmptyList. We can make this work by having EmptyList return the null string, which clearly is not same method as defined in 1.
- L contains two elements: (a, b).toString() returns "(a b)". As above, we can decompose this representation into "(" + "a" + " b" + ")", where "a" is the string representation of _first of L and " b" is some string representation of _rest of L. Clearly " b" cannot be the toString() of _rest as defined in 2.

The above examples suggests defining a method for IList to return the following string representation.

L is an EmptyList: the null string.
L is an NEList: the elements of L are listed in order separated by a space with a leading space preceding the first element and with no space trailing the last element.

This method is called a helper (or auxiliary) method for toString(). Let's name it toStringHelp(). Again as with toString(), to craft an algorithm for toStringHelp(), we first examine a few simple examples and follow the composite design coding pattern.

L is an EmptyList: ().toStringHelp() returns ""; no-brainer here.
L is NEList: Again, we always think of decomposing the problem into processing _first and _rest (which itself is an IList).
- L contains a single element: (a).toStringHelp() returns " a". One possible decomposition of this representation is " " + "a" + "", where "a" is the string representation of _first of L. In this case, _rest is an EmptyList. Clearly, we can make this work by having EmptyList return the null string, which is exactly the same method as defined in 1.
- L contains two elements: (a, b).toStringHelp() returns "(a b)". As above, we can decompose this representation into " " + "a" + " b", where "a" is the string representation of _first of L and " b" is some string representation of _rest of L. Clearly " b" is exactly the toStringHelp() of _rest as defined in 2.

The above examples clearly suggest that toStringHelp() is recursive and need not call on any new helper method. The table below shows the code for toStringHelp().

interface IList
public String toStringHelp();
EmptyList	NEList Object _first; IList _rest;
public String toStringHelp() { return ""; }	public String toStringHelp() { return " " + _first + _rest.toStringHelp(); }

The toString() method simply calls on _rest to perform toStringHelp() to complete the task. This is an example of what is called "delegation". Delegation is an important paradigm in object-oriented programming. We will see more of it in examples to come.

interface IList
No need to declare the toString() method here since it is inherited from Object
EmptyList	NEList Object _first; IList _rest;
public String toString() { return "()"; // Obvious, isn't it? }	public String toString() { // Don't want to do all the processing here! // Delegate to _rest to help complete the task: return "(" + _first + _rest.toStringHelp() + ")"; // Note that this method is not recursive. }

More Exercises:

"Zip" this list with an input list in such a way that the elements in the resulting list alternate between the elements in this list and the elements in the input list. For example, when we Zip (1 2) with (6 7 8), we get (1 6 2 7 8). Notice the lists need not have the same length. Do we need a helper or not?
Merge two sorted lists of Integers to obtain a third sorted list. Do we need a helper or not?

2. Using Accumulators

Sometimes when we process the rest of a non-empty list, we need to pass to this rest some additional information in order for it to help complete the list processing. The idea here is as we traverse the list, we accumulate additional information and pass the information on to the remaining part of the list. For that reason, we call the additional information, 'accumulator'. The following algorithm, called reverse(), to reverse a list illustrates this technique.

Again to craft reverse(), we examine a few simple examples and try to decompose the task of reversing into a task of processing _fist and a task of processing _rest in the non-empty case. The idea here is to accumulate the elements of the list in the reverse order as we traverse the list and pass the accumulated reversed list to the rest to continue the accumulation. By the time we reach the end of the list, that is _rest is empty, the accumulated reversed list is the reverse of the original list.

L is an EmptyList: ().reverse() returns (); no-brainer here.
L is NEList: we can do some processing on _first and ask _rest to do some processing itself. However we do not know what _rest is.
- L contains a single element: (a).reverse() returns (a). Here _rest is empty. The reverse of all the elements preceding _rest is (a). But _rest has no intrinsic knowledge of that unless we pass that information to _rest so that it can decide what to do with it. In this case, _rest simply returns the accumulated information. This is clearly not the method reverse() as define in 1.
- L contains two elements: (a, b).reverse() returns (b a). Here _rest is (b). The reverse of all the elements preceding _rest is (a). But _rest has no intrinsic knowledge of that unless we pass that information to _rest so that it can decide what to do with it. In this case, _rest can "cons" 'b' into (a) and pass the updated accumulated information to its own rest to complete the task.
- L contains three elements: (a, b, c).reverse() returns (c b a). Here _rest is (b, c). The reverse of all the elements preceding _rest is (a). But _rest has no intrinsic knowledge of that unless we pass that information to _rest so that it can decide what to do with it. In this case, _rest can "cons" b into (a) and pass the updated accumulated information to its own rest, (c), to complete the task. When (c) gets the updated accumulator, (c) simply "conses" 'c' into (b a) to get (c b a) and passes it to its rest, which is empty, to complete the task. The empty rest knows what to do here: simply return the accumulated list.

The above suggests writing a helper method, reverseHelp(IList acc), to help reverse() complete its task. The following two tables show the code for reversing a list.

interface IList
public IList reverseHelp(IList acc);
EmptyList	NEList Object _first; IList _rest;
public IList reverseHelp(IList acc) { return acc; }	public IList reverseHelp(IList acc) { // "cons" _first into the accumulator: acc = new NEList(_first, acc); return _rest.reverseHelp(acc); } Remark: the call _rest.reverseHelp(acc) is the last computation in the reverseHelp(IList acc) method and thus is said to be "tail-recursive". A smart compiler will translate tail recursion to a loop in order to save time and space resulting in multifold gain in speed.

interface IList
public IList reverse();
EmptyList	NEList Object _first; IList _rest;
public IList reverse() { return this; // this is a key word representing the object that is executing this method. // Here, this is an empty list. }	public IList reverse() { // create the list that is the reverse of all the elements preceding _rest: IList acc = new NEList(_first, new EmptyList()); // pass the accumulated reverse list to _rest // and ask it to help complete the task. return _rest.reverseHelp(acc); }

3. Using Helper (or Auxiliary) Method

Recall UML diagram illustrating the general composite pattern.

composite.gif (7317 bytes)

As illustrated by the toString() and reverse() methods, there are many situations in which an operation is not directly recursive and may call on "helper" operations on the sub-components to carry out the task. The coding pattern for an operation that requires a helper is as follows.

class Composite extends AComponent {
    // fields and sub-components.

    public Object doTask (Object input) {
      // Process the input parameter and the data fields to obtain a temporary result needed by the sub-components to help complete the task:
        Object temp = process (data fields, input);

      // Pass the temporary result to each of the sub-components asking each of them to "help" complete the task:
        Object pr1 = _part1.helpDoTask (temp); // partial result 1.
        Object pr2 = _part2.helpDoTask (temp);
        // etc...
        Object prN = _partN.helpDoTask (temp);

        // Reassemble the partial results computed by the sub-components to obtain the final result:
        return putTogether (pr1, pr2, ..., prN);
    }

    protected Object helpDoTask (Object input) {
      // Process the input parameter and the data fields to obtain a temporary result needed by the sub-components to help complete the task:
        Object temp = processPartial (data fields, input);

        // Reassemble the partial results computed by the sub-components to obtain the final result:
        return putTogetherPartial (pr1, pr2, ..., prN);
    }
}

class Basic extends AComponent {
    // fields

    public Object doTask (Object input) {
      // Process the input parameter and the data fields to obtain the result:
        return simpleProcess (data fields, input);
    }

    protected Object helpDoTask (Object input) {
      // Process the input parameter and the data fields to obtain the result:
        return simpleProcessPartial (data fields, input);
    }
}

Exercises:

Design an algorithm to compute the length of a list using the accumulator technique.
Design an algorithm to compute the minimum of a list containing Integer objects. When the list is empty, throw an exception.

D. X. Nguyen, last revised 01/26/06