Chapter 1, Building Abstractions with Procedures

Section - Formulating Abstractions with Higher-Order Procedures

Exercise 1.33


Procedure for filtered-accumulate:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define (filtered-accumulate filter combiner null-value term a next b)
  (define (iter a result)
    (if (> a b) result        
        (iter
             (next a)
             (if (filter a)                     
                 (combiner result (term a))
                 result                          
             )
        )
     )
  )
  (iter a null-value)
)

Here is the procedure to sum squares of prime numbers in the specified range:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(define (prime-sum a b)
    (filtered-accumulate prime? + 0 square a inc b)
)

(define (square x) (* x x))

(define (prime? n)
  (= n (smallest-divisor n)))

(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))

Procedure to find product of co-primes less than $n$:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))
  )
)

(define (identity x) x)


(define (prod-of-rel-prime n)
   (define (rel-prime? k)
       (= (gcd k n) 1)
   )
   (filtered-accumulate rel-prime? * 1 identity 1 inc (- n 1))
)