Higher-Order Procedures - Procedures that manipulate other procedures

To use higher-order procedures a language must provided functions as first-class elements. Elements are said to be first class if:

• They may be named by variables
• They may be passed as arguments to procedures
• They may be returned as the results of procedures
• They may be included in data structures

As programmers, we should be alert to opportunities to identify the underlying abstractions in our programs and to build upon them and generalize them to create more powerful abstractions. This is not to say that one should always write programs in the most abstract way possible; expert programmers know how to choose the level of abstraction appropriate to their task. (pg [76][pg76]) [pg76]: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.4

Exercise 1.29

Write a procedure which uses Simpson's Rule to compute the integral of a function f.

(define (simpson-rule f a b n)
  (define h (/ (- b a) n))
  (define (y k) (f (+ a (* k h))))
  (define (simpson-step k)
    (* (cond ((or (= k 0) (= k n)) 1)
             ((even? k) 2)
             (else 4))
       (y k)))
  (/ (* (sum simpson-step 0 inc n)
        (/ h 3))
     1.0))

I've omitted the setup for this, defining sum and inc procedures. The important part is to keep track of k because it determines the value of y_k, and also what factor multiply that value by.

Exercise 1.30

Write an iterative process of the sum procedure.

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

Use result to store the previous computations, return when completed. If not finished increase the current step a and add computation to the result total.

Exercise 1.31

Write a product procedure analogous to the sum procedure. Show how to define factorial in terms of product. Also compute π/4 in terms of product.

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

;; Iterative Solution
(define (product-iter term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* result (term a)))))
  (iter a 1))

Most everything is the same, except for the * procedure. Biggest thing to note is that the null-value here must be a one instead of a zero like in the sum procedure.

(define (inc n) (+ 1 n))
(define (identity n) n)

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

(factorial 5)
;Value: 120

Factorial: 5! = 1*2*3*4*5

(define (plus2 n) (+ n 2))
(define (pair base)
  (* (/ (- base 1) base)
     (/ (+ base 1) base)))

(define (slice-of-pi significant)
  (product pair 3.0 plus2 (+ (* significant 2) 1)))

(define (pi significant)
  (* 4 (slice-of-pi significant)))

(pi 1000)
;Value: 3.142377365093871

The real workhorse is the pair procedure.

I decided to go for the whole pie instead of only a quarter of it. Note that this method is only accurate to the 2nd decimal place with a significant of 1000. Not a very good way to get some pi.

Exercise 1.32

Abstract both sum and product into a more general accumulate procedure.

;; Recursive Solution
(define (accumulate combiner null-value term a next b)
  (if (> a b)
    null-value
    (combiner (term a)
              (accumulate combiner null-value term (next a) next b))))

;; Iterative Solution
(define (accumulate-iter combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
      result
      (iter (next a) (combiner result (term a)))))
  (iter a null-value))

Taking note of the only parts that changed when writing the product procedure from the sum, it's easy to see an abstracted solution.

;; Recursive Sum
(define (sum term a next b)
  (accumulate + 0 term a next b))
;; Iterative Product
(define (product-iter term a next b)
  (accumulate * 1 term a next b))

And the appropriate sum and product from using the new accumulate procedure.

Exercise 1.33

Write a filtered-accumulate. Using this, write sum-squares on an interval a to b. And the product of all positive integers less than n that are relatively prime to n.

;; Recursive Solution
(define (filtered-accumulate filter? combiner null-value term a next b)
  (cond ((> a b) null-value)
        ((filter? a) (combiner (term a)
                               (filtered-accumulate filter? combiner null-value term (next a) next b)))
        (else null-value)))

;; Iterative Solution
(define (filtered-accumulate-iter filter? combiner null-value term a next b)
  (define (iter a result)
    (cond ((> a b) result)
          ((filter? a) (iter (next a) (combiner result (term a))))
          (else (iter (next a) result))))
  (iter a null-value))

An alternative form wasn't requested, but it was simple to do anyway. The book says this is a more general version of accumulate. I guess that's because you could write a filter which doesn't actually filter anything. Hmm. Anyway. Simple enough, just accept a new operand filter? and pass it the value of each a on every iteration. If it passes, accumulate the results, if it fails try the (next a).

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

(sum-sq-primes 1 3)
;Value: 38

Give the filtered-accumulate a test for primality, and add it all up.

;; Product of positive integers less than n that are relatively prime to n
;; uhh... wat?
(define (wat n)
  (define (wat? i)
    (= 1 (gcd i n)))
  (filtered-accumulate-iter wat? * 1 identity 1 inc n))

(wat 10)
;Value: 189

Using the gcd for a filter, multiply all integers that pass the test.

Exercise 1.34

The procedure f will throw an error. In a roundabout way, it will try to apply the argument 2 to the procedure 2, but 2 is a primitive number and not a procedure. Causing the error.

(define (f g)
  (g 2))

;; Process shape
(f f)
(f 2)
(2 2)

Exercise 1.35

Show that the golden ratio is a fixed point of the transformation x -> 1 + 1/x, and use this fact to compute φ by means of the fixed-point procedure.

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)

Exercise 1.36

Print out the guess at every iteration.

(fixed-point (lambda (x) (/ (log 1000) (log x))) 1.5)
(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 1.5)

Results

(fixed-point (lambda (x) (/ (log 1000) (log x))) 1.5)
guess: 1.5
guess: 17.036620761802716
guess: 2.436284152826871
guess: 7.7573914048784065
guess: 3.3718636013068974
guess: 5.683217478018266
guess: 3.97564638093712
guess: 5.004940305230897
guess: 4.2893976408423535
guess: 4.743860707684508
guess: 4.437003894526853
guess: 4.6361416205906485
guess: 4.503444951269147
guess: 4.590350549476868
guess: 4.532777517802648
guess: 4.570631779772813
guess: 4.545618222336422
guess: 4.562092653795064
guess: 4.551218723744055
guess: 4.558385805707352
guess: 4.553657479516671
guess: 4.55677495241968
guess: 4.554718702465183
guess: 4.556074615314888
guess: 4.555180352768613
guess: 4.555770074687025
guess: 4.555381152108018
guess: 4.555637634081652
guess: 4.555468486740348
guess: 4.555580035270157
guess: 4.555506470667713
guess: 4.555554984963888
guess: 4.5555229906097905
guess: 4.555544090254035
guess: 4.555530175417048
;Value: 4.555539351985717

(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 1.5)
guess: 1.5
guess: 9.268310380901358
guess: 6.185343522487719
guess: 4.988133688461795
guess: 4.643254620420954
guess: 4.571101497091747
guess: 4.5582061760763715
guess: 4.555990975858476
guess: 4.555613236666653
guess: 4.555548906156018
guess: 4.555537952796512
;Value: 4.555536087870658

Exercise 1.37

Define a procedure cont-frac such that evaluating (cont-frac n d k) computes the value of the k-term finite continued fraction. Check your procedure by approximating 1/φ

;; Recursive
(define (cont-frac n d k)
  (define (recurse i)
    (if (= i k)
      (/ (n i) (d i))
      (/ (n i) (+ (d i) (recurse (+ i 1))))))
  (recurse 1))

;; Iterative
(define (cont-frac-iter n d k)
  (define (iter r i)
    (if (= 0 i)
        r
        (iter (/ (n i) (+ (d i) r)) (- i 1))))
  (iter 0 k))

Exercise 1.38

Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler's expansion.

(define (e-minus-two k)
  (cont-frac (lambda (i) 1.0)
             (lambda (i) (if (= 0 (remainder (- i 5) 3))
                             (* 2 (+ 2 (/ (- i 5) 3)))
                             1))
             k))

;; Test
;; e - 2 = .71828
(e-minus-two 10)
;Value: .7182817182817183

Exercise 1.39

Define a procedure (tan-cf x k) that computes an approximation to the tangent function based on Lambert's formula.

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

The trickiest part of this problem is subtraction of the next n_k/d_k. Noting that for all values of k except when k = 1 this subtraction is needed, this is solved with a simple condition.

Exercise 1.40

Define a procedure cubic that can be used together with the newtons-method procedure to approximate zeros of the cubic x³ + ax² + bx + c

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

Exercise 1.41

Define a procedure double that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice

(define (double p)
  (lambda (x) (p (p x))))

Exercise 1.42

Define a procedure compose that implements composition. The composition f after g is defined to be the function x -> f(g(x))

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

Exercise 1.43

Write a procedure that takes as inputs a procedure that computes f and a positive integer n and returns the procedure that computes the nth repeated application of f.

(define (repeated f n)
  (if (< n 1)
    (lambda (x) x)
    (compose f (repeated f (- n 1)))))

Exercise 1.44

Write a procedure smooth that takes as input a procedure that computes f and returns a procedure that computes the smoothed f

(define dx 0.0001)

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

Exercise 1.45

Implement a simple procedure for computing nth roots using fixed-point, average-damp, and the repeated procedure of exercise 1.43.

The first thing I need to know is how many times to repeat average-damp. To do this I wrote most of my code for nth-root, with a hard-coded value of 2 for repeating average-damp. Then I started testing from the 4th root onward.

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

((nth-root 4) 16)
;Value: 2.
((nth-root 5) 32)
;Value: 2.0000000945616985
((nth-root 6) 64)
;Value: 2.0000001833403775
((nth-root 7) 128)
;Value: 2.0000003557852426
((nth-root 8) 256) ;; Hangs here. We need to average-damp again.

The repetition for average-damp is log₂(n), so nth-root becomes:

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

Exercise 1.46

Write a procedure iterative-improve that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess.

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

First I redefined the sqrt procedure in terms of iterative-improve

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

Then I rewrote fixed-point and wrote another version of sqrt to test it.

(define (fixed-point f first-guess)
  (define (close-enough? guess)
    (< (abs (- guess (f guess))) tolerance))
  ((iterative-improve close-enough? f) first-guess))

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