1 minute read

Section 1.3.4 - Procedures as Returned Values

Exercise 1.40

cubic will create and return procedures that should be solved using Newton’s method:

(define (cubic a b c)
  (lambda (x) (+ (cube x)
                 (* a (square x))
                 (* b x)
                 c)))

Exercise 1.41

Defining double is quite simple:

(define (double f)
  (lambda (x) (f (f x))))

All the fun comes when trying to calculate something like ((double (double double)) inc).

(double double) essentially returns a procedure that applies the original prodecure 4 times. Therefore (double (double double)) will apply what it receives receives \(4 * 4 = 16\) times. So if we start from \(5\):

> (((double (double double)) inc) 5)
; => 21

Exercise 1.42

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

Exercise 1.43

(define (repeated f n)
  (if (= n 1)
      f
      (repeated (compose f f) (dec n))))

Exercise 1.44

Using the definition of dx from above:

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

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

Exercise 1.45

So the general function would be something like:

(define (root-n x n damps)
  (fixed-point-of-transform
    (lambda (y) (/ x (expt y (- n 1))))
    (repeated average-damp damps)
    1.0))

The parameter damps controls the number of repeated average damps. Experimenting a bit showed that with 2 average damps we can calculate up to the 7th root. 3 average damps lets us calculate up to the 31st root. Using 4 damps we were able to calculate at least up to the 512th root with no problems.

Exercise 1.46

We first define iterative-improve. Note that it returns an anonymous procedure that itself creates and executes a recursive procedure:

(define (iterative-improve good-enough? improve)
  (lambda (guess)
    (define (iter last-guess)
      (if (good-enough? last-guess)
        last-guess
        (iter (improve last-guess))))
    (iter guess)))

Now we can implement sqrt and fixed-point:

(define (sqrt x)
  ((iterative-improve
    (lambda (guess)
      (< (abs (- (square guess) x)) 0.001))
    (lambda (guess)
      (average guess (/ x guess))))
   1.0))

(define (fixed-point f first-guess)
  ((iterative-improve
    (lambda (guess)
      (< (abs (- guess (f guess))) tolerance))
    (lambda (guess) (f guess)))
   first-guess))

This concludes Chapter 1. Onwards to Chapter 2 then!

Updated: