2.2 Hierarchical Data and the Closure Property

Hierarchical Data and the Closure Property

As we have seen, pairs provide a primitive glue that we can use to construct compound data objects. Figure 2.4 shows a standard way to visualize a pair—in this case, the pair formed by pair(1, 2).

In this representation, which is called box-and-pointer notation, each compound object is shown as a pointer to a box. The box for a pair has two parts, the left part containing the head of the pair and the right part containing the tail.

Figure 2.4

Box-and-pointer representation of pair(1, 2).

We have already seen that pair can be used to combine not only numbers but pairs as well. (You made use of this fact, or should have, in doing exercises 2.2 and 2.3.) As a consequence, pairs provide a universal building block from which we can construct all sorts of data structures. Figure 2.6 shows two ways to use pairs to combine the numbers 1, 2, 3, and 4.

Figure 2.6

Two ways to combine 1, 2, 3, and 4 using pairs.

The ability to create pairs whose elements are pairs is the essence of list structure's importance as a representational tool. We refer to this ability as the closure property of pair. In general, an operation for combining data objects satisfies the closure property if the results of combining things with that operation can themselves be combined using the same operation.

[1]

Closure is the key to power in any means of combination because it permits us to create hierarchical structures—structures made up of parts, which themselves are made up of parts, and so on.

From the outset of chapter 1, we've made essential use of closure in dealing with functions, because all but the very simplest programs rely on the fact that the elements of a combination can themselves be combinations. In this section, we take up the consequences of closure for compound data. We describe some conventional techniques for using pairs to represent sequences and trees, and we exhibit a graphics language that illustrates closure in a vivid way.

[1]

The use of the word closure here comes from abstract algebra, where a set of elements is said to be closed under an operation if applying the operation to elements in the set produces an element that is again an element of the set. The programming languages community also (unfortunately) uses the word closure to describe a totally unrelated concept: A closure is an implementation technique for representing functions with free names. We do not use the word closure in this second sense in this book.

< Previous

Next >

2.2

Hierarchical Data and the Closure Property