SICP Exercise 1.44: Smoothed Functions

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.

Now the book already gives us "some small number" for dx, which was defined in the section on Newton's method as:

(define dx 0.00001)

The selection of dx is fairly arbitrary here, but it'll do for this exercise where we'll reuse dx in producing smooth:

(define (smooth f)
  (lambda (x) (/ (+ (f (- x dx))
                    (f x)
                    (f (+ x dx)))
                 3)))

Our definition of smooth simply calculates f(x - dx), f(x), and f(x + dx), sums them and divides by 3 to produce the mean.

To calculate the n-fold smoothed function we simply produce the procedure that will apply smooth n times to a function, and pass f to this:

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

Let's see it in action:

> (square 6.48074)
41.9999909476
> ((smooth square) 6.48074)
41.99999094766667
> ((n-fold-smooth square 1) 6.48074)
41.99999094766667
> ((n-fold-smooth square 2) 6.48074)
41.99999094773333
> ((n-fold-smooth square 3) 6.48074)
41.99999094779999
> ((n-fold-smooth square 4) 6.48074)
41.99999094786666
> ((n-fold-smooth square 5) 6.48074)
41.99999094793333
> ((n-fold-smooth square 10) 6.48074)
41.999990948266635

SICP Exercise 1.43: Compose... Again... and Again... and Again...

If f is a numerical function and n is a positive integer, then we can form the n^th repeated application of f, which is defined to be the function whose value at x is f(f(...(f(x))...)). For example, if f is the function x→x + 1, then the n^th repeated application of f is the function x→x + n. If f is the operation of squaring a number, then the n^th repeated application of f is the function that raises its argument to the 2^nth power. Write a procedure that takes as inputs a procedure that computes f and a positive integer n and returns the procedure that computes the n^th repeated application of f. Your procedure should be able to be used as follows:

> ((repeated square 2) 5)
625

Hint: You may find it convenient to use compose from exercise 1.42.

First of all, let's just clarify what we're asked for here. We're not being asked to define a procedure that can take, for example, (lambda (x) (+ x 1)) and the value n and return the procedure (lambda (x) (+ x n)). Instead we're being asked to define a procedure that returns a procedure that computes the n^th repeated application of f. I.e. it applies f n times in sequence.

We're also given a nice hint. We can use compose to do this. And we can do this with an iterative procedure. How? Well, compose allows us to combine two single-parameter procedures together to produce a procedure that is the result of applying the first to the result of the second. All we need to do is to start with f as our result, and iterate from 1..n, at each step composing the result so far with another application of f, until we reach n, at which point we'll have our desired procedure:

(define (repeated f n)
  (define (iter i result)
    (if (= i n)
        result
        (iter (+ i 1) (compose f result))))
  (iter 1 f))

Of course we can be a bit smarter about this... Back in section 1.2.4 we learned about the successive squaring approach to exponentiation. We can use a similar approach for producing the procedure that calculates the n^th repeated application of f by noting that:

• When n is even, (repeated f n) ≡ (compose ff ff), where ff is defined as (repeated f (/ n 2)).
• When n is odd, (repeated f n) ≡ (compose f (repeated f (- n 1)))

While this won't save us any steps when we're actually calculating the n^th repeated application of f to a value, it will save steps in the evaluation of repeated and the procedure produced will likely have a more compact representation. Here's the smarter version:

(define (repeated f n)
  (cond ((= n 1) f)
        ((even? n) (let ((ff (repeated f (/ n 2))))
                     (compose ff ff)))
        (else (compose f (repeated f (- n 1))))))

And to confirm this works:

> ((repeated square 2) 5)
625
> (define add10 (repeated inc 10))
> (add10 5)
15
> (add10 20)
30
> (add10 (add10 3))
23

SICP Exercise 1.42: Composing Functions

Let f and g be two one-argument functions. The composition f after g is defined to be the function x→f(g(x)). Define a procedure compose that implements composition. For example, if inc is a procedure that adds 1 to its argument,

((compose square inc) 6)
49

After the last exercise, this one is nice and easy. All the procedure compose needs to do is to produce a lambda expression that takes a single parameter, applies g to that parameter and then applies f to the result of that:

(define (compose f g)
  (lambda (x) (f (g x))))

And just to confirm it works:

> ((compose square inc) 6)
49