SICP exercise 1.44

From Drewiki

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).

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:

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

Test it:

Output:

0

Output:

6

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.

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.

Output:

2

Output:

1.55555555555556

Output:

1.40740740740741

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 , where s is the smoothing function, and it occurs n times. We can use repeated from the exercise 1.43 to implement it:

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.

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

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

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

Output:

2

Output:

2

Output:

1.55555555555556

Output:

1.40740740740741

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!