| << Chapter < Page | Chapter >> Page > |
Is
a list?
Is
a list?
Is there a list that follows butter in the above?
A non-empty list is a list that has an element called first and a list called rest.
Note that in the above formulation, the rest of a list is itself a list! The definition of a list is an example of what we call a recursive definition: the list contains a substructure that is isomorphic to itself.
The UML diagram below captures the recursive data definition of the list data structure.
This definition translates into Java code as follows.
/**
* Represents the abstract list structure.*/
public interface IList {} | |
/**
* Represents empty lists.*/
public class MTList implements IList {} |
/**
* Represents non-empty lists.*/
public class NEList implements IList {private Object _first;
private IList _rest;} |
The above is an example of what is called the composite design pattern . The composite pattern is a structural pattern that prescribes how to build a container object that is composed of other objects whose structures are isomorphic to that of the container itself. In this pattern, the container is called a composite. In the above, IList is called the abstract component, MTList is called the basic component and NEList is called the composite. The composite design pattern embodies the concept of recursion , one of the most powerful thinking tool in computing. (There is a subject in theoretical computer science and mathematics called "recursive function theory," which studies the meaning of what computing means and in effect defines in the most abstract form what a computer is and what it can and cannot do.)
Now that we have defined what a list is, we ask ourselves how we can process it? What can we do with a list? The above code makes it clear that there is not a whole lot we can do with a list besides instantiating a bunch of MTList objects via the call new MTList() (why?). Now that we are using the full Java language, we need to write a constructor for NEList in order to instantiate non-empty list objects with appropriate first and rest. The Java code for NEList now looks as follows (note how the comments are written).
/**
* Represents non-empty lists.*/
public class NEList implements IList {private Object _first;
private IList _rest;/**
* Initializes this NEList to a given first and a given rest.* @param f the first element of this NEList.
* @param r the rest of this NEList.*/
public NEList(Object f, IList r) {_first = f;
_rest = r;}
}
The list structure as coded in the above is completely encapsulated , that is, all internal components (if any) of a list are private and cannot be accessed by any external code. Using the appropriate constructors, we can make a bunch of lists to store data but we cannot retrieve data nor do anything with these lists. In Object-Oriented Programming (OOP) parlance, the list is said to have no behavior at all. As such they are of no use to us.
In order to perform any meaningful list processing at all, we need to program more "intelligence" into the list structure by adding appropriate methods to the list to provide the desired behaviors. So instead of asking what we can do with a list, the right question to ask in OOP is "what can a list do for us?" Let us start by presenting a few simple tasks that we want a list to perform and try to figure out how an "intelligent" list would carry out such tasks via some role acting.
Notification Switch
Would you like to follow the 'Principles of object-oriented programming' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|