1 665c255d 2023-08-04 jrmu ;; Exercise 1.33. 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:
5 665c255d 2023-08-04 jrmu (define (filtered-accumulate combiner filter null-value term a next b)
8 665c255d 2023-08-04 jrmu (if (filter a)
9 665c255d 2023-08-04 jrmu (combiner (term a)
10 665c255d 2023-08-04 jrmu (filtered-accumulate combiner filter null-value term (next a) next b))
11 665c255d 2023-08-04 jrmu (filtered-accumulate combiner filter null-value term (next a) next b))))
13 665c255d 2023-08-04 jrmu (define (sum-prime-squares a b)
14 665c255d 2023-08-04 jrmu (filtered-accumulate +
17 665c255d 2023-08-04 jrmu (lambda (x) (* x x))
22 665c255d 2023-08-04 jrmu (define (smallest-divisor n)
23 665c255d 2023-08-04 jrmu (find-divisor n 2))
25 665c255d 2023-08-04 jrmu (define (find-divisor n test-divisor)
26 665c255d 2023-08-04 jrmu (cond ((> (square test-divisor) n) n)
27 665c255d 2023-08-04 jrmu (( divides? test-divisor n) test-divisor)
28 665c255d 2023-08-04 jrmu (else (find-divisor n (+ test-divisor 1)))))
30 665c255d 2023-08-04 jrmu (define (divides? a b)
31 665c255d 2023-08-04 jrmu (= (remainder b a) 0))
33 665c255d 2023-08-04 jrmu (define (prime? n)
34 665c255d 2023-08-04 jrmu (= n (smallest-divisor n)))
37 665c255d 2023-08-04 jrmu ;; (define (accumulate combiner null-value term a next b)
38 665c255d 2023-08-04 jrmu ;; (if (> a b)
39 665c255d 2023-08-04 jrmu ;; null-value
40 665c255d 2023-08-04 jrmu ;; (combiner (term a)
41 665c255d 2023-08-04 jrmu ;; (accumulate combiner null-value term (next a) next b))))
43 665c255d 2023-08-04 jrmu ;; (define (sum term a next b)
44 665c255d 2023-08-04 jrmu ;; (accumulate + 0 term a next b))
45 665c255d 2023-08-04 jrmu ;; (define (product term a next b)
46 665c255d 2023-08-04 jrmu ;; (accumulate * 1 term a next b))
49 665c255d 2023-08-04 jrmu ;; (define (accumulate combiner null-value term a next b)
50 665c255d 2023-08-04 jrmu ;; (if (> a b)
51 665c255d 2023-08-04 jrmu ;; null-value
52 665c255d 2023-08-04 jrmu ;; (combiner (term a)
53 665c255d 2023-08-04 jrmu ;; (accumulate combiner null-value term (next a) next b))))
55 665c255d 2023-08-04 jrmu ;; (define (accumulate-iter combiner null-value term a next b)
56 665c255d 2023-08-04 jrmu ;; (define (iter i result)
57 665c255d 2023-08-04 jrmu ;; (if (> a b)
59 665c255d 2023-08-04 jrmu ;; (iter (next i) (combiner (term i) result))))
60 665c255d 2023-08-04 jrmu ;; (iter a null-value))
63 665c255d 2023-08-04 jrmu ;; (define (factorial n)
64 665c255d 2023-08-04 jrmu ;; (product (lambda (x) x)
66 665c255d 2023-08-04 jrmu ;; (lambda (x) (+ x 1))
69 665c255d 2023-08-04 jrmu ;; (define (factorial-iter n)
70 665c255d 2023-08-04 jrmu ;; (product-iter (lambda (x) x)
72 665c255d 2023-08-04 jrmu ;; (lambda (x) (+ x 1))
75 665c255d 2023-08-04 jrmu ;; pi/4 = 2*4*4*6*6*8*...
76 665c255d 2023-08-04 jrmu ;; ---------------
77 665c255d 2023-08-04 jrmu ;; 3*3*5*5*7*7*...
79 665c255d 2023-08-04 jrmu ;; (define (pi iterations)
81 665c255d 2023-08-04 jrmu ;; (product (lambda (x)
82 665c255d 2023-08-04 jrmu ;; (if (odd? x)
83 665c255d 2023-08-04 jrmu ;; (/ (+ x 1) (+ x 2))
84 665c255d 2023-08-04 jrmu ;; (/ (+ x 2) (+ x 1))))
86 665c255d 2023-08-04 jrmu ;; (lambda (x) (+ x 1))
87 665c255d 2023-08-04 jrmu ;; iterations)))
89 665c255d 2023-08-04 jrmu (define (test-case actual expected)
90 665c255d 2023-08-04 jrmu (load-option 'format)
92 665c255d 2023-08-04 jrmu (format #t "Actual: ~A Expected: ~A" actual expected))
94 665c255d 2023-08-04 jrmu ;; (test-case (factorial 0) 1)
95 665c255d 2023-08-04 jrmu ;; (test-case (factorial 1) 1)
96 665c255d 2023-08-04 jrmu ;; (test-case (factorial 2) 2)
97 665c255d 2023-08-04 jrmu ;; (test-case (factorial 3) 6)
98 665c255d 2023-08-04 jrmu ;; (test-case (factorial 4) 24)
99 665c255d 2023-08-04 jrmu ;; (test-case (factorial 5) 120)
100 665c255d 2023-08-04 jrmu ;; (test-case (factorial 6) 720)
101 665c255d 2023-08-04 jrmu ;; (test-case (factorial 7) 5040)
102 665c255d 2023-08-04 jrmu ;; (test-case (factorial-iter 7) 5040)
104 665c255d 2023-08-04 jrmu ;; (test-case (pi 10000) 3.1415)
106 665c255d 2023-08-04 jrmu ;; 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)
108 665c255d 2023-08-04 jrmu ;; 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).
110 665c255d 2023-08-04 jrmu (test-case (sum-prime-squares 2 17) 666)
112 665c255d 2023-08-04 jrmu (define (relatively-prime-product n)
113 665c255d 2023-08-04 jrmu (filtered-accumulate *
114 665c255d 2023-08-04 jrmu (lambda (i)
115 665c255d 2023-08-04 jrmu (= (gcd i n) 1))
117 665c255d 2023-08-04 jrmu (lambda (x) x)
122 665c255d 2023-08-04 jrmu (define (gcd a b)
123 665c255d 2023-08-04 jrmu (if (= b 0)
125 665c255d 2023-08-04 jrmu (gcd b (remainder a b))))
127 665c255d 2023-08-04 jrmu (test-case (relatively-prime-product 20) 8729721)
