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

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 [itex]s(s(s\cdots(s(f))))[/itex], 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!