Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 1.44

From Drewiki
Jump to: navigation, search

Problem

The idea of smoothing a function is an important concept in signal processing. If f is a function and dx is some small number, then the smoothed version of f is the function whose value at a point x is the average of f(x - dx), f(x), and f(x + dx). Write a procedure smooth that takes as input a procedure that computes f and returns a procedure that computes the smoothed f. It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtained the n-fold smoothed function. Show how to generate the n-fold smoothed function of any given function using smooth and repeated from exercise 1.43.

Solution

The implementation of smooth is straightforward; it's just a procedure that returns a procedure that calculates the average of f(x - dx), f(x), and f(x + dx).

(define dx 0.00001)
 
(define (smooth f)
  (define (ave a b c) (/ (+ a b c) 3))
  (lambda (x)
    (ave (f (- x dx)) (f x) (f (+ x dx)))))

Let's test it with an impulse function, i.e, a function which is zero for all input values except exactly one input value a, where it is non-zero. This impulse-maker procedure returns a procedure whose value is y at input value a, and zero everywhere else:

(define (impulse-maker a y)
  (lambda (x)
    (if (= x a)
        y
        0)))

Here's an impulse function whose value is 6 at x=0:

(define my-impulse-function
  (impulse-maker 0 6))

Test it:

(my-impulse-function -1)

Output:

0
(my-impulse-function 0)

Output:

6
(my-impulse-function (+ 0 dx))

Output:

0


Now let's smooth it at x=0: we expect this combination to have the value 2, as (0 + 6 + 0)/3 = 2.

((smooth my-impulse-function) 0)

Output:

2


Good.

Successive smoothings should gradually reduce the impulse function to a smoothed "hump" where the largest value of the smoothed function (at x=0) gradually converges to zero. Here's how we apply those successive smoothings by hand. The results shown are from Chicken Scheme 3.1 on a MacBook Pro running Mac OS X 10.5.

((smooth (smooth my-impulse-function)) 0)

Output:

2
((smooth (smooth (smooth my-impulse-function))) 0)

Output:

1.55555555555556
((smooth (smooth (smooth (smooth my-impulse-function)))) 0)

Output:

1.40740740740741
((smooth (smooth (smooth (smooth (smooth my-impulse-function))))) 0)

Output:

1.25925925925926


The exercise asks for a procedure which implements an n-fold smoothing function. This procedure should return another procedure that calculates the n-fold smoothed function of any given input function. This is just the composition of s and f that results in <math>s(s(s\cdots(s(f))))</math>, where s is the smoothing function, and it occurs n times. We can use repeated from the exercise 1.43 to implement it:

(define (compose f g)
  (lambda (x) (f (g x))))
 
(define (inc x) (+ x 1))
 
(define (repeated f n)
  (define (repeated-iter i result)
    (if (= i n)
        result
        (repeated-iter (inc i) (compose f result))))
  (repeated-iter 1 f))

Note that the n-fold smoothing function generator should return a procedure, not a numeric value, where the function looks like (lambda (x) (s(s(s...(s(f))))) x), per the constructed-by-hand examples above. What we need to do is to use the compose procedure to compose multiple occurrences of smooth, n times. We can use repeated for this. Then we apply the result of these n compositions of smooth to the procedure that calculates the function we wish to smooth. That resulting procedure can then be applied to a numerical argument when we want to evaluate the smoothed function at that argument.

(define (n-fold-smooth f n)
  ((repeated smooth n) f))

n-fold-smooth first composes n smooths, creating a procedure which, when expanded, looks like

(lambda (x) (smooth (smooth (smooth... (smooth x)))))

It then applies that procedure to f to produce another procedure which expands to

(lambda (x) ((smooth (smooth (smooth... (smooth f)))) x))

Now let's test our generator. We should get the same answers that we got with our constructed-by-hand examples:

((n-fold-smooth my-impulse-function 1) 0)

Output:

2
((n-fold-smooth my-impulse-function 2) 0)

Output:

2
((n-fold-smooth my-impulse-function 3) 0)

Output:

1.55555555555556
((n-fold-smooth my-impulse-function 4) 0)

Output:

1.40740740740741
((n-fold-smooth my-impulse-function 5) 0)

Output:

1.25925925925926


Note that in this exercise, we used compose not to create a composition of procedures which take numeric arguments, as we did in exercise 1.43 with the square procedure; but rather to create a composition of procedures which take procedure arguments. The same method of composition works for both types of procedures!

Personal tools