Structure and Interpretation of Computer Programs

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)

---