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