...

The above implementation is an example of what is called the Composite Design Pattern. The composite design pattern is a structural pattern that prescribes how to build a container object that is composed of other objects whose structure is isomorphic to that of the container itselfspecial case of the union pattern where one or more of the variants for the union type T contains fields of root type T. In this pattern, the container union is called a composite. Here the container object union type is IntList and the list and variant ConsIntList is said to be a composite : because it is a list and is composed of a substructure that is itself a listincludes a field of type IntList.

The composite pattern also prescribes a coding pattern for the container's its methods: when a container variant is called to perform an operation, it traverses through its list fields of composed objects root type and call calls on them to perform the same operation. It allows the a client to treat the container and what it contains uniformly by making use of an instance of type T and it embedded instances uniformly using polymorphism.

This coding pattern is called the interpreter design pattern: we are interpreting it interprets the abstract behavior of a class in each of the its concrete subclasses. The composite pattern is a pattern refers to express the the structure of a systemthe composite type hierarchy, while the interpreter pattern is used to express the behaviors (i.e. methods) of the systemrefers to how the behavior of the variants of the type are defined uniformly via polymorphism.

Interpreter Design Pattern for List

The interpreter design pattern applied to the above composite list structure prescribes a coding pattern for list operations that is analogous to Scheme function template. It entails declaring an abstract method for each list operation in the abstract list class, IntList, and defining corresponding concrete methods in the concrete list subclasses: the empty list class, EmptyIntList, and the non-empty class, ConsIntList. The concrete method for EmptyIntList corresponds to the base case in the Scheme function template while the concrete method in ConstIntList corresponds to the recursive case by calling the same method on its rest.

The following is the coding template for the interpreter design pattern for IntList and its subclasses.

...