Formulating Abstractions with Higher-Order Procedures Exercises

1.3

(define (cube x) (* x x x))

Procedures as Arguments

Imports: 1.3 cube

Mathematicians long ago created an abstraction for summations:

\sum_{n=a}^{b}f(n) = f(a) + f(a+1) + \dots + f(b).

We can do the same in Scheme using a higher-order procedure:

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

(define (inc n) (+ n 1))
(define (sum-cubes a b) (sum cube a inc b))
(sum-cubes 1 10) => 3025

(define (identity x) x)
(define (sum-integers a b) (sum identity a inc b))
(sum-integers 1 10) => 55

(define (pi-sum a b)
  (define (pi-term x) (/ 1.0 (* x (+ x 2))))
  (define (pi-next x) (+ x 4))
  (sum pi-term a pi-next b))
(* 8 (pi-sum 1 1000)) ~> 3.139592655589783

The definite integral of a function $f$ between limits $a$ and $b$ can be approximated numerically using the formula

\int_{a}^{b} = \left[f(a+\frac{dx}{2}) + f(a + dx + \frac{dx}{2}) + f(a + 2dx + \frac{dx}{2}) + \dots \right]dx

for small values of $dx$ . We can express this directly as a procedure:

(define (integral f a b dx)
  (define (add-dx x)
    (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

(integral cube 0 1 0.01) ~> .24998750000000042
(integral cube 0 1 0.001) ~> .249999875000001

Exercise 1.29

Imports: 1.3 cube, Procedures as Arguments inc sum

Simpson’s rule provides a more accurate method of numerical integration:

\begin{aligned} \int_{a}^{b}f \approx \dfrac{h}{3}[y_{0} + 4y_{1} + 2y_{2} + 4y_3 + 2y_4 + \dots + 2y_{n-2} + 4y_{n-1} + y_n]dx \\ \text{where} \ \ \ \ h = \frac{b-a}{n} \ \ \ \ \text{and} \ \ \ \ \ y_k= f(a+kh) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{aligned}

The even integer $n$ controls the accuracy of the approximation.

(define (simpson f a b n)
  (let ((h (/ (- b a) n)))
    (define (term k)
      (* (f (+ a (* k h)))
         (if (or (= k 0) (= k n))
             1
             (+ 2 (* 2 (remainder k 2))))))
    (* h 1/3 (sum term 0.0 inc n))))

Simpson’s rule gives an exact answer for $\int_{0}^{1} x^3 dx$ when $n = 2$ :

(simpsone cube 0 1 2) => 0.25

Exercise 1.30

(define (sum term a next b)
  (define (iter a acc)
    (if (> a b)
        acc
        (iter (next a) (+ acc (term a)))))
  (iter a 0))

Exercise 1.31

Imports: Procedures as Arguments identity inc

a. Recursive:

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

b. Iterative:

(define (product term a next b)
  (define (iter a acc)
    (if (> a b)
        acc
        (iter (next a) (* acc (term a)))))
  (iter a 1))

Calculating factorials and approximating $\pi$ using product:

(define (factorial n)
  (product identity 1 inc n))

(factorial 5) => 120
(factorial 7) => 5040

(define (approx-pi n)
  (define (term k)
    (let ((r (remainder k 2)))
      (/ (+ k 2 (- r))
         (+ k 1 r))))
  (* 4 (product term 1.0 inc n)))

(approx-pi 00010) ~> 3.2751010413348065
(approx-pi 00100) ~> 3.1570301764551654
(approx-pi 01000) ~> 3.1431607055322552
(approx-pi 10000) ~> 3.1417497057380084

Exercise 1.32

Imports: Procedures as Arguments identity inc

a. Recursive:

(define (accumulate combine id term a next b)
  (if (> a b)
      id
      (combine (term a)
               (accumulate combine id term (next a) next b))))

b. Iterative:

(define (accumulate combine id term a next b)
  (define (iter a acc)
    (if (> a b)
        acc
        (iter (next a) (combine (term a) acc))))
  (iter a id))

Implementing sum and product in terms of accumulate:

(define (sum term a next b)
  (accumulate + 0 term a next b))

(define (product term a next b)
  (accumulate * 1 term a next b))

(sum identity 1 inc 10) => 55
(product identity 1 inc 10) => 3628800

Exercise 1.33

Imports: Compound Procedures square, Procedures as Arguments identity inc, Exercise 1.23 prime?

define (filtered-accumulate combine pred? id term a next b)
  (define (iter a acc)
    (cond ((> a b) acc)
          ((pred? a)
           (iter (next a) (combine (term a) acc)))
          (else (iter (next a) acc))))
  (iter a id))

a. Sum of squares primes in the interval from a to b:

(define (sum-squared-primes a b)
  (filtered-accumulate + prime? 0 square a inc b))

(sum-squared-primes 10 15) => 290

b. Product of positive integers below n relatively prime to n:

(define (product-rel-prime n)
  (define (rel-prime? i)
    (= (gcd i n) 1))
  (filtered-accumulate * rel-prime? 1 identity 1 inc (- n 1)))

(product-rel-prime 10) => (* 3 7 9)

Constructing Procedures Using Lambda

Imports: Compound Procedures square

((lambda (x y z) (+ x y (square z))) 1 2 3) => 12

Exercise 1.34

Imports: Compound Procedures square

(define (f g) (g 2))

(f square) => 4
(f (lambda (z) (* z (+ z 1)))) => 6

If we try evaluating the combination (f f), we get the process (f f) => (f 2) => (2 2). This fails because 2 is not a procedure:

(f f) =!> "2"

Procedures as General Methods

Finding roots of equations by the half-interval method

Imports: Example: Square Roots by Newton’s Method average

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))

(define tolerance 0.001)
(define (close-enough? x y) (< (abs (- x y)) tolerance))

Half interval method: $\Theta(\log (|a-b|/t))$ time where $t$ is tolerance.

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error 'half-interval-method
                  "values are not of opposite sign"
                  a b)))))

(half-interval-method sin 2.0 4.0)
~> 3.14111328125
(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3)) 1.0 2.0)
~> 1.89306640625
(half-interval-method cos -1 1)
=!> "values are not of opposite sign: -1 1"

Finding fixed points of functions

Imports: Example: Square Roots by Newton’s Method average

(define tolerance 0.00001)
(define (close-enough? x y) (< (abs (- x y)) tolerance))

(define (fixed-point f first-guess)
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point cos 1.0) ~> 0.7390822985224023

Without average damping, it does not converge:

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y)) 1.0))

(sqrt 2) =>...

With average damping, it converges:

(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y))) 1.0))

(sqrt 2) ~> 1.4142135623746899

Exercise 1.35

Imports: Finding fixed points of functions fixed-point

Theorem. The golden ratio $\varphi$ is a fixed point of the transformation $x \mapsto 1 + 1/x$ .

Proof. We will show that for any $x > 1$ and $y = 1 + 1/x$ , we have $|y - \varphi| < |x - \varphi|$ , meaning each iteration bring the value closer to $\varphi$ . Recall from 1.13 the golden ration equation $\varphi + 1 = \varphi^2$ , or equivalently $\varphi = 1+1/\varphi$ :

\begin{aligned} |y - \varphi| &= \left|1 + \frac{1}{x} - \varphi \right| \\ &= \left|\frac{x+1-\varphi x}{x} \right| \\ &= \left| \frac{x+1-(1=1/\varphi)x}{x} \right| \ \ \ \text{since} \ \varphi = 1 +1/\varphi \\ &=\left| \frac{\varphi -x }{x\varphi}\right| \\ &= \frac{|x-\varphi|}{|x\varphi|}. \end{aligned}

(define golden-ratio (/ (+ 1 (sqrt 5)) 2))

golden-ratio
~> 1.6180339887498950
(fixed-point (lambda (x) (+ 1 (/ x))) 1.0)
~> 1.6180327868852458

Exercise 1.36

Imports: Example: Square Roots by Newton’s Method average ,Finding fixed points of functions close-enough?

(define (fixed-point-verbose f first-guess)
  (define (try guess)
    (let ((next (f guess)))
      (display next)
      (newline)
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (f x) (/ (log 1000) (log x)))

Without average damping, it takes 28 approximations.

(hide-output (fixed-point-verbose f 5)) ~> 4.555539314360711
(string-count #\newline (capture-output (fixed-point-verbose f 5))) => 28

With average damping, it takes only 8 approximations.

(define (f-damped x) (average x (f x)))
(hide-output (fixed-point-verbose f-damped 5)) ~> 4.5555361005218895
(string-count #\newline (capture-output (fixed-point-verbose f-damped 5))) => 8

Exercise 1.37

Imports: Exercise 1.35 golden-ratio

a. Recursive process:

(define (cont-frac n d k)
  (define (helper i)
    (if (= i k)
        0
        (/ (n i)
           (+ (d i) (helper (+ i 1))))))
  (helper 1))

b. Iterative process:

(define (cont-frac n d k)
  (define (iter i acc)
    (if (zero? i)
        acc
        (iter (- i 1) (/ (n i)
                         (+ (d i) acc)))))
  (iter k 0))

Approximating the inverse golden ratio using cont-frac:

(define (always-one i) 1.0)
(define (approx-igr k) (cont-frac always-one always-one k))

When $k=11$ , the value is accurate to 4 decimal places:

(approx-igr 01) ~> 1.0
(approx-igr 02) ~> 0.5
(approx-igr 03) ~> 0.6666666666666666
(approx-igr 04) ~> 0.6000000000000001
(approx-igr 05) ~> 0.625
(approx-igr 06) ~> 0.6153846153846154
(approx-igr 07) ~> 0.6190476190476191
(approx-igr 08) ~> 0.6176470588235294
(approx-igr 09) ~> 0.6181818181818182
(approx-igr 10) ~> 0.6179775280898876
(approx-igr 11) ~> 0.6180555555555556

(define (round4 x) (* 1e-4 (truncate (* 1e4 x))))
(round4 (approx-igr 11)) ~> (round4 (/ golden-ratio))

Exercise 1.38

Imports: Exercise 1.37 always-one cont-frac

(define (approx-e k)
  (define (d i)
    (if (zero? (remainder (+ i 1) 3))
        (* 2/3 (+ i 1))
        1))
  (+ 2 (cont-frac always-one d k)))

(approx-e 1) ~> 3.0
(approx-e 2) ~> 2.6666666666666665
(approx-e 3) ~> 2.75
(approx-e 4) ~> 2.7142857142857144
(approx-e 5) ~> 2.71875
(approx-e 1000) ~> 2.7182818284590455

Exercise 1.39

Imports: Compound Procedures square, Exercise 1.37 cont-frac

(define (tan-cf x k)
  (cont-frac
   (lambda (i) (if (= i 1) x (- (square x))))
   (lambda (i) (- (* i 2) 1))
   k))

(define quarter-pi (atan 1))

(tan-cf quarter-pi 1) ~> 0.7853981633974483
(tan-cf quarter-pi 2) ~> 0.9886892399342050
(tan-cf quarter-pi 3) ~> 0.9997876809149684
(tan-cf quarter-pi 4) ~> 0.9999978684156948
(tan-cf quarter-pi 5) ~> 0.9999999865263550
(tan quarter-pi) ~> 1

Procedures as Returned Values

Imports: Compound Procedures square, Example: Square Roots by Newton’s Method average, Finding fixed points of functions fixed-point

(define (average-damp f)
  (lambda (x) (average x (f x))))

((average-damp square) 10) => 55

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))

(define (cbrt x)
  (fixed-point (average-damp (lambda (y) (/ x (square y)))) 1.0))

Newton’s Method

Imports: Compound Procedures square, Finding fixed points of functions fixed-point

(define dx 0.00001)
(define (deriv g)
  (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))

(define (cube x) (* x x x))
((deriv cube) 5) ~> 75.00014999664018

(define (newton-transform g)
  (lambda (x) (- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

(define (sqrt x)
  (newtons-method (lambda (y) (- (square y) x)) 1.0))

Abstractions and first-class procedures

Imports: Compound Procedures square, Example: Square Roots by Newton’s Method average, Finding fixed points of functions fixed-point, Procedures as Returned Values average-damp, Newton’s Method newton-transform

(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (/ x y)) average-damp 1.0))

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (- (square y) x)) newton-transform 1.0))

Exercise 1.40

Imports: Compound Procedures square, Newton’s Method newtons-method

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

(newtons-method (cubic a b c) 1.0) approximates a zero of $x^3 +ax^2 +bx +c$ :

(define f (cubic -3 1 1))
(f (newtons-method f 1.0)) ~> 0

Exercise 1.41

Imports: Procedures as Arguments inc

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

(((double (double double)) inc) 5)
=> (((double (lambda (f) (double (double f)))) inc) 5)
=> (((lambda (f) (double (double (double (double f))))) inc) 5)
=> ((double (double (double (double inc)))) 5)
=> ((double (double (double (lambda (x) (inc (inc x)))))) 5)
=> ((double (double (lambda (x) (inc (inc (inc (inc x))))))) 5)
=> ((double (lambda (x) (inc (inc (inc (inc (inc (inc (inc (inc x)))))))))) 5)
=> ((lambda (x) (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc
      (inc (inc (inc (inc x))))))))))))))))) 5)
=> (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc
     (inc 5))))))))))))))))
=> 21

Exercise 1.42

Imports: Compound Procedures square, Procedures as Arguments inc

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

((compose square inc) 6) => 49

Exercise 1.43

Imports: Compound Procedures square, Exercise 1.42 compose

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

((repeated square 2) 5) => 625

Exercise 1.44

Imports: Compound Procedures square, Exercise 1.43 repeated

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

((smooth square) 2) ~> 4.006666666666667
(((repeated smooth 5) square) 2) ~> 4.033333333333333

Exercise 1.45

Imports: Finding fixed points of functions fixed-point, Procedures as Returned Values average-damp, Exercise 1.43 repeated

We need to average-damp $[\log_{2} n]$ times.

(define (nth-root x n)
  (fixed-point
   ((repeated average-damp
              (floor (/ (log n) (log 2))))
    (lambda (y) (/ x (expt y (- n 1)))))
   1.0))

(nth-root 4 2) ~> 2.000000000000002
(nth-root 256 8) ~> 2.0000000000039666
(nth-root 1048576 20) ~> 1.999999063225966

Exercise 1.46

Imports: Compound Procedures square, Example: Square Roots by Newton’s Method average, Finding fixed points of functions tolerance

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

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

(sqrt 2) ~> 1.4142156862745097

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

This is slightly different from the original fixed-point because it returns guess when it’s good enough, not next (so the original always does one more improvement).

(fixed-point cos 1.0) ~> 0.7390893414033928