[1] If we want to be more formal, we can specify consistent with the interpretations given above to mean that the operations satisfy a collection of rules such as these:
  • For any set S and any object x, (element-of-set? x (adjoin-set x S)) is_element_of_set(x, adjoin_set(x, S)) is true (informally: Adjoining an object to a set produces a set that contains the object).
  • For any sets S and T and any object x, (element-of-set? x (union-set S T)) is_element_of_set(x, union_set(S, T)) is equal to (or (element-of-set? x S) (element-of-set? x T)) is_element_of_set(x, S) || is_element_of_set(x, T) (informally: The elements of (union-set S T) union_set(S, T) are the elements that are in S or in T).
  • For any object x, (element-of-set? x '()) is_element_of_set(x, null) is false (informally: No object is an element of the empty set).
[2] Halving the size of the problem at each step is the distinguishing characteristic of logarithmic growth, as we saw with the fast-exponentiation algorithm of section 1.2.4 and the half-interval search method of section 1.3.3.
[3] We are representing sets in terms of trees, and trees in terms of lists—in effect, a data abstraction built upon a data abstraction. We can regard the procedures functions entry, left-branch, left_branch, right-branch, right_branch, and make-tree make_tree as a way of isolating the abstraction of a binary tree from the particular way we might wish to represent such a tree in terms of list structure.
[4] Examples of such structures include B-trees and red-black trees. There is a large literature on data structures devoted to this problem. See Cormen, Leiserson, Rivest, and Stein 2022.
[5] Exercises 2.672.69 are due to Paul Hilfinger.
2.3.3   Example: Representing Sets