SICP section 1.3 - formulating abstractions with higher-order procedures
The generalised form of
product can be defined (recursively) as follows:
(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))))
(define (sum term a next b) (accumulate + 0 term a next b)) (define (product term a next b) (accumulate * 1 term a next b))
The iterative version of
accumulate uses an internal procedure with two state variables - one tracks the value of \(a\); the other accumulates the result, which is returned when the terminating condition \(a > b\) is met.
(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))
filtered-accumulate is a generalised version of
accumulate that only combines terms that satisfy a given condition. Its implementation is similar to
accumulate, with an added conditional.
(define (filtered-accumulate combiner null-value term a next b filter) (define (next-fa) (filtered-accumulate combiner null-value term (next a) next b filter)) (if (> a b) null-value (if (filter a) (combiner (term a) (next-fa)) (next-fa))))
filtered-accumulate to define a procedure that computes the sum of the squares of prime numbers:
(define (sum-square-prime a b) (filtered-accumulate + 0 square a inc b prime?))
…and a procedure that computes the product of integers less than \(n\) that are relatively prime to \(n\):
(define (gcd a b) (if (= b 0) a (gcd b (remainder a b)))) (define (identity n) n) (define (product-rel-prime n) (define (rel-prime? a) (= (gcd a n) 1)) (filtered-accumulate * 1 identity 1 inc (- n 1) rel-prime?))
Attempting to evaluate
(f f) produces the following error:
mit-scheme : The object 2 is not applicable. dr-racket : application: not a procedure; expected a procedure that can be applied to arguments given: 2 arguments...:
We can use the substitution model to get a clearer picture of the error:
(define (f g) (g 2)) (f f) (f 2) (2 2)
The second invocation of
f attempts to apply \(2\), which is not a procedure, to \(2\). No bueno.
For this exercise, I found that rewriting the k-term finite continued fraction as a single line helped me see more clearly how to implement it as a recursive process:
(define (cont-frac n d k) (define (frac x) (if (= x k) (/ (n x) (d x)) (/ (n x) (+ (d x) (frac (+ x 1)))))) (frac 1))
To obtain an approximation of \(1/φ\) accurate to 4 decimal places, \(k = 10\).
(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 10)
The iterative version of
cont-frac decrements a counter \(x\) that begins with \(k\), accumulates the result in \(acc\), and returns the result when \(x = 0\):
(define (cont-frac-iter n d k) (define (frac x acc) (if (= x 0) acc (frac (- x 1) (/ (n k) (+ (d k) acc))))) (frac k 0))
For this fraction, we know that all values of \(N_i\) are \(1\). \(D_i\) however, is slightly less straightforward. The (convoluted) pattern I derived from the \(D_i\) series is \(2(i + 1)/3\) if \((i + 1) \bmod 3 = 0\), for all \(i > 1\).
(define (d i) (cond ((= i 1) 1) ((not (= (remainder (+ i 1) 3) 0)) 1) (else (/ (* 2 (+ i 1)) 3)))) (+ (cont-frac (lambda (i) 1.0) d 10) 2)
Fairly obvious patterns in both series: \(N_i = -x^2\) for \(i > 1\), and \(D_i = 2i - 1\).
(define (tan-cf x k) (define (n k) (if (= k 1) x (- (square x)))) (define (d k) (- (* 2.0 k) 1)) (cont-frac n d k))
double can be defined as follows:
(define (double f) (lambda (x) (f (f x))))
Applying the substitution model shows us that the procedure makes \(2^4\)
inc calls, which gives us the answer \(5 + 16 = 21\).
(((double (double double)) inc) 5) (((double (lambda (x) (double (double x)))) inc) 5) (((lambda (x) (double (double (double (double x))))) inc) 5) ((double (double (double (double inc)))) 5) ((double (double (double (lambda (x) (inc (inc x)))))) 5) ... ; Expands to 16 `inc` calls 21
(define (compose f g) (lambda (x) (f (g x))))
compose from the previous exercise:
(define (repeated f n) (if (= n 1) (lambda (x) (f x)) (compose (repeated f (- n 1)) f)))
repeated from the previous exercise:
(define dx 0.00001) (define (smooth f) (lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3.0))) (define (n-fold-smooth f n x) ((repeated (smooth f) n) x))
Root | Damps 2 | 1 3 | 1 4 | 2 5 | 2 6 | 2 7 | 2 8 | 3 9 | 3 10 | 3 11 | 3 12 | 3 13 | 3 14 | 3 15 | 3 16 | 4
From this table, we can determine that \(average\_damps = log_2 (root)\), rounded down to the nearest integer.
Scheme does not have a
log procedure that allows us to specify a base. To get around this, we can use the log change-of-base formula: \(log_b n = log_a n / log_a b\).
(define (average x y) (/ (+ x y) 2.0)) (define (average-damp f) (lambda (x) (average x (f x)))) (define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1))))) (define (log-b2 n) (/ (log n) (log 2))) (define (nth-root x n) (fixed-point ((repeated average-damp (inexact->exact (floor (log-b2 n)))) (lambda (y) (/ x (expt y (- n 1))))) 1.0))
As specified in the exercise, the procedure that
iterative-improve should return is one that keeps improving the guess until it is good enough, indicating that it needs to be a procedure that repeatedly calls itself.
For a procedure to call itself, it needs a name - which is why we define an internal procedure and return it. If there is a way to solve this exercise using a
lambda, I have not figured out how.
(define (iterative-improve good-enough? improve) (define (improve-procedure guess) (if (good-enough? guess) guess (improve-procedure (improve guess)))) improve-procedure)
iterative-improve to redefine
(define (average x y) (/ (+ x y) 2)) (define (square x) (* x x)) (define (sqrt x) ((iterative-improve (lambda (guess) (< (abs (- (square guess) x)) 0.001)) (lambda (guess) (average guess (/ x guess)))) 1.0))
; Fixed point (define tolerance 0.00001) (define (fixed-point f first-guess) ((iterative-improve (lambda (guess) (< (abs (- guess (f guess))) tolerance)) (lambda (guess) (f guess))) first-guess))