Given the following task:
You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure. Show how to express the following using filtered-accumulate:
a. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a prime? predicate already written)
b. the product of all the positive integers less than n that are relatively prime to n (i.e., all positive integers i < n such that GCD(i,n) = 1).
I wrote this code:
(define (gcd a b) (if (= b 0) a (gcd b (remainder a b)))) (define (square x) (* x x)) (define (divisible? b a) (= (remainder b a) 0)) (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (define (next x) (if (= x 2) 3 (+ x 2))) (cond ((> (square test-divisor) n) n) ((divisible? n test-divisor) test-divisor) (else (find-divisor n (next test-divisor))))) (define (prime? x) (= (smallest-divisor x) x)) (define (inc x) (+ x 1)) (define (identity x) x)
(define (filtered-accumulate combiner filter null-value term a next b) (if (> a b) null-value (combiner (if (filter a) (term a) null-value) (filtered-accumulate combiner filter null-value term (next a) next b) )))
(define (i-filtered-accumulate combiner filter null-value term a next b) (define (iter a result) (if (> a b) result (iter (next a) (combiner result (if (filter a) (term a) null-value))))) (iter a null-value))
Sum of primes between
(define (sum-of-primes-between a b) (filtered-accumulate + prime? 0 identity a inc b))
Product of relative primes less than
(define (product-of-relative-primes-less-than n) (define (relprime-n i) (= (gcd i n) 1)) (filtered-accumulate * relprime-n 1 identity 1 inc n))
What do you think?