...
- 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:
- 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.
Now, the Java viewpoint on lists:
- Objects "know" what they are. An empty list knows that it is an empty list and does not need to be told such and likewise, non-empty (cons) lists know that they are non-empty and thus have a first and rest.
- Objects have behaviors, i.e. objects contain functions ("methods"). That is, the functions to process an object, e.g. a list, are built into the list. (at least for now).
- Never ask an object what it is. The object already knows. Let the object do what it already knows how to do. Delegate to the object, don't query its type!
- Objects are part of an inheritance hierarchy, which in part, determines their type.
More List Exercises
Recall our object model (common known in the Scheme world as "data definition") for lists of int.
...