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.)
(It is also common to use "curried" versions of functions especially in functional languages.)
list e = atom e | nil | cons (list e × list e)
atomic :list e -> boolean
null :list e -> boolean
head :list e -> list e
tail :list e -> list e
cons :list e × list e -> list e
Rules, for all x:e and L:list e:
atomic(atom(x)) = true
atomic(nil) = atomic(cons(L,L')) = false
null(cons(L,L')) = false
null(atom(x)) = false
head(cons(L,L')) = L
head(nil) = head(atom(x)) = error
tail(cons(L,L')) = L'
tail(nil) = tail(atom(x)) = error
[L1, L2, ..., Ln]
= cons(L1, cons(L2, ...,cons(Ln,nil) ...))
The Hierarchical List Abstract Data Type.
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.
The map function, as previously defined, applies a function
to every element of a list.
There is no difficulty if those elements are themselves lists.
reverse( [1, [2,3], 4] ) = [4, [2, 3], 1]
map(reverse, [[1,2,3], [4,5,6,7]])
= [[3,2,1], [7,6,5,4]]
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.
Note that this version of flatten potentially takes O(n2) time
An O(n) version which does not use append
is possible using an accumulating parameter.
flatten(nil) = nil |
flatten(atom(e)) = [e] |
flatten(cons(L,L')) = append(flatten(L),flatten(L'))
eg. flatten [1, [2, 3], 4] = [1, 2, 3, 4]
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.
If one of these cases is missing it is probably the sign of an error.
The atomic and null cases are usually very simple, often returning
a simple function of the atom or a constant value.
This leaves only the constructed case.
Here the result often involves a recursive call of the function on
one or both of the sublists.
As an example, consider counting the atoms in a list:
f( atom(e) ) = ... |
f( nil ) = ... |
f( cons(L,L') ) = ...often f(L) and/or f(L')...
Match this instance of a function against the general pattern given previously.
count( atom(e) ) = 1 | % count atoms in list
count( nil ) = 0 |
count( cons(L,L') ) = count(L)+count(L')
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 some
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
This necessitates trivial changes to some
of the routines previously defined on flat lists.
For example, the sieve of Eratosthenes is given below in this new guise.
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,
Trees can be used to represent hierarchical data,
such as a business organisation.
They share this ability with hierarchical lists and
the connection is much stronger; there
is a way of representing such a tree by a list.
. . .
. . .
. . .
2 3 4
. . .
. . .
5 6 7
The technique is to link siblings together into a list.
| | |
| | |
| | |
| nil |
5-->6 nil 7 nil
Tree Transformed into a List.
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:
Testing on [1,2,3,4] would give the correct answer 4.
Testing on [1,[2,3],4] would produce the incorrect answer 3 rather than
the correct answer 4 and a diagnosis should easily follow.
Care is needed however because testing on [1,,3,4] would not show
the error up.
badcount(atom(e)) = 1 |
badcount(nil) = 0 |
badcount(cons(L,L')) = 1+badcount(L')
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.
- An element at the top level of a list is said to be at a depth of 1.
If L' is a sublist at depth 1 of L and x is at depth d of L'
then x is at depth d+1 of L.
Write a function to find the depth of the deepest element of a list.
- Write a routine to `reflect' a hierarchical list so that
the list and all sublists are reversed as if seen in a mirror.
- Write a fast O(n) time routine to flatten a hierarchical list of n cells.
eg. flatten [1, [[2, 3], 4], 5] = [1, 2, 3, 4, 5].
- Use a hierarchical list to represent the structure of (part of)
your university or institute.
This may contain faculties, schools and departments or
perhaps it has other "layers".
It will probably be necessary to add extra information fields to
the list cells.
- Modify the routine that prints a list so
that it makes use of indentation to represent
Note that there is no single best answer to this problem;
the ideal style is a matter of taste.
eg. [1, 2, [3, 4, 5], [6, [7, 8]]] -->
[3, 4, 5],
- Convert the list printing routine, PutList, into iterative,
Department of Computer Science, UWA 1984-86.