This chapter considers hierarchical lists after the style of the programming language Lisp. Where the lists of a previous chapter were flat or one-level. Hierarchical lists contain both atomic elements and sublists. This allows them to store structured data and they are general enough to be the only structured data type of the programming language Lisp. (Any serious computer scientist is strongly recommended to read The LISP 1.5 Programmer's Manual by J. McCarthy et al, M.I.T. Press 1962.)
There is a convention that lists do not terminate in an atom. This could be enforced by making cons(L,atom(e)) an error.
Most of the operations on flat lists also work on hierarchical lists. Note however that a sublist is considered to be an element so that reversal of a list will not reverse its sublists.
Hierarchical lists allow information with substructure to be stored. Some list operations are only applicable to hierarchical lists. For example, such a list can be flattened.
There are three alternative cases in the definition of the new list type - atomic, empty or non-empty. This means that most functions for manipulating lists have three cases in their definition.
Implementation of Hierarchical Lists
The most natural way to implement the new list type is with pointers and records although arrays can also be used. The empty list can be represented by the nil pointer but there are two other cases and these must be implemented by a union.
There are two classes of node or cell in these lists; the tag `t' indicates the class of a cell. An atomic cell contains an element. A cons cell points to two sublists; by convention the second is always non-atomic.
If this implementation can be assumed, it is faster to substitute in-line code for the basic operations rather than to call the routines.
Because a list structure can now contain sublists to an arbitrary depth, printing a list becomes more complex.
Note that this routine uses a loop to iterate along the elements of the list. Recursion is used to print a sublist. The recursion can proceed to an arbitrary depth to match the list structure.
Because there is no implicit conversion from the element type to an atomic list, it is necessary to have a routine to construct an atomic cell. This necessitates trivial changes to some of the routines previously defined on flat lists.
Lists and Trees
A (rooted) tree structure consists of nodes (or vertices) and arcs (or edges). A special ancestral node is called the root. An arc points from a parent node to each of its child nodes, if any.
Trees are very important in computing. A common type is the binary tree where each node has at most two descendants; it is the subject of the next chapter.
Testing and Debugging
The techniques of testing and debugging that apply to flat lists are if anything even more useful in the case of hierarchical lists. Pre and postconditions and assertions should be used wherever possible. Flat lists can only have problems of contents and termination. A hierarchical list can also have problems of incorrect structure. For this reason an output routine is very important so as to be able to print list values when things go wrong.
There are just three types of list - atomic, empty and non-empty. This realisation reduces the apparent complexity of lists and makes systematic testing and debugging possible. The key cases are an atom, nil, and a list of a "few" elements. If a case is missing from a routine it probably indicates an error. Depending on the application, the third case may include a small number of examples of different nesting structure.
For example, we might have written the following incorrect function to count the atoms in a list:
In general, testing can show a program to be wrong but can never prove it to be correct. Nevertheless judicious testing as an adjunct to program verification can add to confidence in a program. Matching test cases to the structure of a data type and to the structure of the routines acting on it leads to fast systematic testing and debugging.