Using this, we can compute the sum of the cubes of the integers from 1 to 10:
(sum-cubes 1 10)
3025
With the aid of an identity procedure to compute the term, we can define
sum-integers
in terms of
sum
:
(define (identity x) x)
(define (sum-integers a b)
(sum identity a inc b))
Then we can add up the integers from 1 to 10:
(sum-integers 1 10)
55
We can also define
pi-sum
in the same way:
50
(define (pi-sum a b)
(define (pi-term x)
(/ 1.0 (* x (+ x 2))))
(define (pi-next x)
(+ x 4))
(sum pi-term a pi-next b))
Using these procedures, we can compute an approximation to :
(* 8 (pi-sum 1 1000))
3.139592655589783
Once we have
sum
, we can use it as a building block in formulating further concepts. For instance, the
definite integral of a function
f between
the limits a and
b can be approximated numerically using the
formula
for small values of
dx. We can express this directly as a procedure:
(define (integral f a b dx)
(define (add-dx x) (+ x dx))
(* (sum f (+ a (/ dx 2.0)) add-dx b)
dx))
(integral cube 0 1 0.01)
.24998750000000042
(integral cube 0 1 0.001)
.249999875000001
(The exact value of the integral of
cube
between 0 and 1 is 1/4.)
Exercise 1.29. Simpson’s Rule is a more accurate method of numerical integration than the method
illustrated above. Using Simpson’s Rule, the integral of a function f between a and b is approximated
as
where h = (b - a)/n, for some even integer n, and y
k
= f(a + kh). (Increasing n increases the accuracy of
the approximation.) Define a procedure that takes as arguments f, a, b, and n and returns the value of
the integral, computed using Simpson’s Rule. Use your procedure to integrate
cube
between 0 and 1
(with
n = 100 and
n = 1000), and compare the results to those of the
integral
procedure shown
above.
Exercise 1.30. The
sum
procedure above generates a linear recursion. The procedure can be rewritten
so that the sum is performed iteratively. Show how to do this by filling in the missing expressions in
the following definition:
(define (sum term a next b)
(define (iter a result)
(if <??>
<??>
(iter <??> <??>)))
(iter <??> <??>))
Exercise 1.31.
a. The
sum
procedure is only the simplest of a vast number of similar abstractions that can be
captured as higher-order procedures.
51
Write an analogous procedure called
product
that returns
the product of the values of a function at points over a given range. Show how to define
factorial
in terms of
product
. Also use
product
to compute approximations to using the formula
52
b. If your
product
procedure generates a recursive process, write one
that generates an iterative
process. If it generates an iterative process, write one that generates a recursive process.
Exercise 1.32. a. Show that
sum
and
product
(exercise 1.31) are both special cases of a still more
general notion called
accumulate
that combines a collection of terms, using some general
accumulation function:
(accumulate combiner null-value term a next b)
Accumulate
takes as arguments the same term and range specifications as
sum
and
product
,
together with a
combiner
procedure (of two arguments) that specifies how the current term is to be
combined with the accumulation of the preceding terms and a
null-value
that specifies what base
value to use when the terms run out. Write
accumulate
and show how
sum
and
product
can both
be defined as simple calls to
accumulate
.
b. If your
accumulate
procedure generates a recursive process, write one that generates an iterative
process. If it generates an iterative process, write one that generates a recursive process.
Exercise 1.33. You can obtain an even more general version of
accumulate
(exercise 1.32) by
introducing the notion of a filter on the terms to be combined. That is, combine only those terms
derived from values in the range that satisfy a specified condition. The resulting
filtered-accumulate
abstraction takes the same arguments as accumulate, together with an
additional predicate of one argument that specifies the filter. Write
filtered-accumulate
as a
procedure. Show how to express the following using
filtered-accumulate
:
a. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a
prime?
predicate already written)
b. the product of all the positive integers less than n that are relatively prime to n (i.e., all positive
integers i < n such that GCD(i,n) = 1).
1.3.2 Constructing Procedures Using
Lambda
In using
sum
as in section 1.3.1, it seems terribly awkward to have to define trivial procedures such as
pi-term
and
pi-next
just so we can use them as arguments to our higher-order procedure. Rather
than define
pi-next
and
pi-term
, it would be more convenient to have
a way to directly specify
‘‘the procedure that returns its input incremented by 4’’ and ‘‘the procedure that returns the reciprocal
of its input times its input plus 2.’’ We can do this by introducing the special form
lambda
, which
creates procedures. Using
lambda
we can describe what we want as
(lambda (x) (+ x 4))
and
(lambda (x) (/ 1.0 (* x (+ x 2))))
Then our
pi-sum
procedure can be expressed without defining any auxiliary procedures as
(define (pi-sum a b)
(sum (lambda (x) (/ 1.0 (* x (+ x 2))))
a
(lambda (x) (+ x 4))
b))
Again using
lambda
, we can write the
integral
procedure without having to define the auxiliary
procedure
add-dx
:
(define (integral f a b dx)
(* (sum f
(+ a (/ dx 2.0))
(lambda (x) (+ x dx))
b)
dx))
In general,
lambda
is used to create procedures in the same way as
define
, except that no name is
specified for the procedure:
(lambda (<formal-parameters>) <body>)