You are here

Home » Principles of Object-Oriented Programming » Immutable List Structure » List Structure and the Interpreter Design Pattern » List Processing

What can a list do?

26 July, 2019 - 09:51
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at http://cnx.org/contents/402b20ad-c01f-45f1-9743-05eadb1f710e@37.6

Length of a list

Suppose we are given a list L and asked to find out how many elements it has. What should we do? The temptation here is to start thinking about "traversing" the list and keep a count as we go along, and when we encounter the "end" of the list, the count should be the number of elements in the list. But how do we know that that's the right answer? In order to determine whether or not the result obtained by counting as one traverses the list from beginning to end is correct, we have to define what it means to be the number of elements in the list. The number of elements in a list is an abstract notion, isn't it? In order to define such a quantity, we need to go back to the definition of what a list is.

  • A list is an abstract notion of a container structure.
  • An empty list is a list that has no element     
  • A non-empty list is a list that has an element called first and a list called rest.

To define the notion of the number of elements in a list, we need to define what we mean by the number of elements in an empty list and what we mean by the number of elements in a non-empty list.

  • The number of elements in a list is an abstract notion because the list is an abstract notion.
  • The number of elements of an empty list is 0.
  • The number of elements in a non-empty list that contains first and rest is 1 plus the number of elements in rest.

The definition of the number of elements in a list is thus recursive. The recursive characteristic of this definition arises naturally from the recursive characteristic of the list structure. Whatever approach we use to compute the number of elements in a list, in order to prove correctness, we must show that the result satisfies the above definition.

Here is the code for the above computation.

Table 3.1 Top-level abstract list denition
package listFW;
/**
* Represents the abstract list structure.
*/
public interface IList {
        /**
        * Abstract notion of the number of elements in this IList.
        */
        public int getLength();
}
 
Table 3.2 Concrete list implementations
package listFW;
/**
 * Represents empty lists.
 */ public class MTList implements IList {
/**
* The number of elements in an
* empty list is zero.
*/
public int getLength() {
return 0;
}
}








  		package listFW;
/**
* Represents non-empty lists.
*/
public class NEList implements IList {
private Object _first;
private IList _rest;
// Constructor ommitted.

/**
* The number of elements in a
   non-empty
* list is the number of elements
   of its
* rest plus 1.
*/
public int getLength() {
return 1 + _rest.getLength();
}
}
 

The above coding pattern is an example of what is called the interpreter design pattern: we are inter¬preting the abstract behavior of a class (or interface) in each of the concrete subclasses (or implementations). The composite pattern is a pattern to express the structure of a system, while the interpreter pattern is used to express the behaviors (i.e. methods) of the system. The interpreter pattern is usually applied to coding methods in a composite structure. In a later lecture, we shall see another way of expressing the behavior of a composite structure without having to add new methods and interpret them.

  • 1072 reads