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.
Exercise 2.30. Define a procedure
square-tree
analogous to the
square-list
procedure of
exercise 2.21. That is,
square-list
should behave as follows:
(square-tree
(list 1
(list 2 (list 3 4) 5)
(list 6 7)))
(1 (4 (9 16) 25) (36 49))
Define
square-tree
both directly (i.e., without using any higher-order procedures) and also by
using
map
and recursion.
Exercise 2.31. Abstract your answer to exercise 2.30 to produce a procedure
tree-map
with the
property that
square-tree
could be defined as
(define (square-tree tree) (tree-map square tree))
Exercise 2.32. We can represent a set as a list of distinct elements, and we can represent the set of all
subsets of the set as a list of lists. For example, if the set is
(1 2 3)
, then the set of all subsets is
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
. Complete the following definition of a
procedure that generates the set of subsets of a set and give a clear explanation of why it works:
(define (subsets s)
(if (null? s)
(list nil)
(let ((rest (subsets (cdr s))))
(append rest (map <??> rest)))))
2.2.3 Sequences as Conventional Interfaces
In working with compound data, we’ve stressed how data abstraction permits us to design programs
without becoming enmeshed in the details of data representations, and how abstraction preserves for
us the flexibility to experiment with alternative representations. In this section, we introduce another
powerful design principle for working with data structures -- the use of conventional interfaces.
In section 1.3 we saw how program abstractions, implemented as higher-order procedures, can capture
common patterns in programs that deal with numerical data. Our ability to formulate analogous
operations for working with compound data depends crucially on the style in which we manipulate our
data structures. Consider, for example, the following procedure, analogous to the
count-leaves
procedure of section 2.2.2, which takes a tree as argument and computes the sum of the squares of the
leaves that are odd:
(define (sum-odd-squares tree)
(cond ((null? tree) 0)
((not (pair? tree))
(if (odd? tree) (square tree) 0))
(else (+ (sum-odd-squares (car tree))
(sum-odd-squares (cdr tree))))))
On the surface, this procedure is very different from the following one, which constructs a list of all
the even Fibonacci numbers Fib(k), where k is less than or equal to a given integer n:
(define (even-fibs n)
(define (next k)
(if (> k n)
nil
(let ((f (fib k)))
(if (even? f)
(cons f (next (+ k 1)))
(next (+ k 1))))))
(next 0))
Despite the fact that these two procedures are structurally very different, a more abstract description of
the two computations reveals a great deal of similarity. The first program
enumerates the leaves of a tree;
filters them, selecting the odd ones;
squares each of the selected ones; and
accumulates the results using
+
, starting with 0.
The second program
enumerates the integers from 0 to n;
computes the Fibonacci number for each integer;
filters them, selecting the even ones; and
accumulates the results using
cons
, starting with the empty list.
A signal-processing engineer would find it natural to conceptualize these processes in terms of signals
flowing through a cascade of stages, each of which implements part of the program plan, as shown in
figure 2.7. In
sum-odd-squares
, we begin with an enumerator, which generates a ‘‘signal’’
consisting of the leaves of a given tree. This signal is passed through a filter, which eliminates all but
the odd elements. The resulting signal is in turn passed through a map, which is a ‘‘transducer’’ that
applies the
square
procedure to each element. The output of the map is then fed to an accumulator,
which combines the elements using
+
, starting from an initial 0. The plan for
even-fibs
is
analogous.
Figure 2.7: The signal-flow plans for the procedures
sum-odd-squares
(top) and
even-fibs
(bottom) reveal the commonality between the two programs.
Figure 2.7: The signal-flow plans for the procedures
sum-odd-squares
(top) and
even-fibs
(bottom) reveal the commonality between the two programs.
Unfortunately, the two procedure definitions above fail to exhibit this signal-flow structure. For
instance, if we examine the
sum-odd-squares
procedure, we find that the enumeration is
implemented partly by the
null?
and
pair?
tests and partly by the tree-recursive structure of the
procedure. Similarly, the accumulation is found partly in the tests and partly in the addition used in the
recursion. In general, there are no distinct parts of either procedure that correspond to the elements in
the signal-flow description. Our two procedures decompose the computations in a different way,
spreading the enumeration over the program and mingling it with the map, the filter, and the
accumulation. If we could organize our programs to make the signal-flow structure manifest in the
procedures we write, this would increase the conceptual clarity of the resulting code.
Sequence Operations
The key to organizing programs so as to more clearly reflect the signal-flow structure is to concentrate
on the ‘‘signals’’ that flow from one stage in the process to the next. If we represent these signals as
lists, then we can use list operations to implement the processing at each of the stages. For instance,
we can implement the mapping stages of the signal-flow diagrams using the
map
procedure from
section 2.2.1:
(map square (list 1 2 3 4 5))
(1 4 9 16 25)
Filtering a sequence to select only those elements that satisfy a given predicate is accomplished by
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
For example,
(filter odd? (list 1 2 3 4 5))
(1 3 5)
Dostları ilə paylaş: |