The representation of sequences in terms of lists generalizes
naturally to represent sequences whose elements may
themselves be sequences. For example, we can regard the object
((1 2) 3 4) constructed by
(cons (list 1 2) (list 3 4))
as a list of three items, the first of which is itself a list,
(1 2). Indeed, this is suggested by the form in which the result is
printed by the interpreter. Figure 2.5 shows
the representation of this structure in terms of pairs.
Another way to think of sequences whose elements are sequences is as trees. The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees. Figure 2.6 shows the structure in figure 2.5 viewed as a tree.
Recursion is a natural tool for dealing with tree structures, since
we can often reduce operations on trees to operations on their
branches, which reduce in turn to operations on the branches of the
branches, and so on, until we reach the leaves of the tree.
As an example, compare the
length procedure of
section 2.2.1 with the
count-leaves procedure, which
returns the total number of leaves of a tree:
(define x (cons (list 1 2) (list 3 4)))
(list x x)(((1 2) 3 4) ((1 2) 3 4))
(length (list x x))2
(count-leaves (list x x))8
count-leaves, recall the recursive plan for computing
Lengthof a list
xis 1 plus
Lengthof the empty list is 0.
Count-leaves is similar. The value for the empty list is the same:
Count-leavesof the empty list is 0.
But in the reduction step, where we strip off the
car of the list, we must take into account that the
car may itself be a tree whose leaves we need to count. Thus, the appropriate reduction step is
Count-leavesof a tree
Finally, by taking
cars we reach actual leaves, so we need another base case:
Count-leavesof a leaf is 1.
To aid in writing recursive procedures on trees, Scheme provides the primitive
pair?, which tests whether its argument is a pair.
Here is the complete procedure:
(define (count-leaves x) (cond ((null? x) 0) ((not (pair? x)) 1) (else (+ (count-leaves (car x)) (count-leaves (cdr x))))))
Mapping over trees
map is a powerful abstraction for dealing with sequences,
map together with recursion is a powerful abstraction for dealing with trees. For instance, the
scale-tree procedure, analogous to
section 2.2.1 takes as arguments a numeric factor and a tree whose leaves are numbers. It returns a tree of the same shape,
where each number is multiplied by the factor. The recursive plan for
scale-tree is similar to the one for
(define (scale-tree tree factor) (cond ((null? tree) nil) ((not (pair? tree)) (* tree factor)) (else (cons (scale-tree (car tree) factor) (scale-tree (cdr tree) factor))))) (scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 10)(10 (20 (30 40) 50) (60 70))
Another way to implement
scale-tree is to regard the
tree as a sequence of sub-trees and use
map. We map
over the sequence, scaling each sub-tree in turn, and return the list
of results. In the base case, where the tree is a leaf, we simply
multiply by the factor:
(define (scale-tree tree factor) (map (lambda (sub-tree) (if (pair? sub-tree) (scale-tree sub-tree factor) (* sub-tree factor))) tree))
Many tree operations can be implemented by similar combinations of sequence operations and recursion.
condmatters, since the empty list satisfies
null?and also is not a pair. [back]