2 minute read

Section 1.3 - Formulating Abstractions With Higer-Order Procedures

Section 1.3.1 - Procedures as Arguments

Exercise 1.29

Here is the implementation of Simpson’s Rule. Note that we defined h as a procedure with no arguments since we haven’t learned about let yet.

(define (integral-simon f a b n)
  (define (h) (/ (- b a) n))
  (define (y k) (* (f (+ a (* k (h))))
                   (cond ((or (= k 0) (= k n)) 1)
                         ((even? k) 2)
                         (else 4))))
  (* (sum y 0 inc n)
     (/ (h) 3.0)))

And running it we can see that it converges faster than the previous solution:

> (integral-simon cube 0.0 1 100)
0.24999999999999992
> (integral-simon cube 0.0 1 1000)
0.2500000000000003

Exercise 1.30

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

Exercise 1.31

product is very similar to sum:

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

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

;; We can use it:

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

(define (wallis n)
  (define (term a) (if (even? a)
                       (/ (+ a 2) (+ a 1))
                       (/ (+ a 1) (+ a 2))))
  (* (product term 1.0 inc n) 4))

;; Let's try
(wallis 100)

And we can write the iterative version:

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

Exercise 1.32

This is a recursive version of accumulate:

(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))))

We can use it to build sum and product:

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

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

And we can write the iterative version:

(define (accumulate 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))

Exercise 1.33

We just skip the combiner if the predicate is not satisfied:

(define (filtered-accumulate f combiner null-value term a next b)
  (if (> a b)
      null-value
      (if (f a)
          (combiner
           (term a)
           (filtered-accumulate f combiner null-value term (next a) next b))
          (filtered-accumulate f combiner null-value term (next a) next b))))

Then we can define the procedure that generates the sum of squares of primes between a and b, and the procedure that generates the product of relative primes less than n:

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

(define (product-relative-primes n)
  (define (relative-prime? a) (= (gcd a n) 1))
  (filtered-accumulate relative-prime? * 1 identity 1 inc (- n 1)))

Updated: