1.33
练习 1.33 你可以通过引进一个处理被组合项的过滤器（filter）概念，写出一个比accumulate（练习1.32）更一般的版本。也就是说，在计算过程中，只组合起由给定范围得到的项里的那些满足特定条件的项。这样得到的filtered-accumulate抽象取与上面累积过程同样的参数，再加上一个另外的描述有关过滤器的谓词参数。请写出filtered-accumulate作为一个过程，说明如何用filtered-accumulate表达以下内容：
a）求出在区间a到b中所有素数之和（假定你已经写出了谓词prime?）。
b）小于n的所有与n互素的正整数（即所有满足GCD(i, n)=1的整数i < n）之乘积。
a) 迭代实现：
(define (filtered-accumulate filter combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result(if (filter a)
(iter (next a) (combiner result (term a )))
(iter (next a) result))))
(iter a null-value))
(define (always-true x) true)
(define (accumulate combiner null-value term a next b)
(filtered-accumulate always-true combiner null-value term a next b))
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
(define (cube x) (* x x x))
(define (inc x) (+ x 1))
(sum cube 1 inc 10)
(define (identity x) x)
(product identity 1 inc 10)
(define (smallest-divisor n)
(find-divisor n 2))
(define (square x) (* x x))
(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? x y)
(= (remainder y x) 0))
(define (prime? x) (= x (smallest-divisor x)))
(prime? 1)
(prime? 2)
(prime? 3)
(prime? 4)
(define (sum-prime-numbers a b)
(filtered-accumulate prime? + 0 identity a inc b))
(sum-prime-numbers 1 10)
(+ 1 2 3 5 7)
3025
3628800
true
true
true
false
18
18
3628800
true
true
true
false
18
18
b) 迭代实现：
(define (filtered-accumulate filter combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result(if (filter a)
(iter (next a) (combiner result (term a )))
(iter (next a) result))))
(iter a null-value))
(define (always-true x) true)
(define (accumulate combiner null-value term a next b)
(filtered-accumulate always-true combiner null-value term a next b))
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
(define (cube x) (* x x x))
(define (inc x) (+ x 1))
(sum cube 1 inc 10)
(define (identity x) x)
(product identity 1 inc 10)
(define (smallest-divisor n)
(find-divisor n 2))
(define (square x) (* x x))
(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? x y)
(= (remainder y x) 0))
(define (prime? x) (= x (smallest-divisor x)))
(prime? 1)
(prime? 2)
(prime? 3)
(prime? 4)
(define (sum-prime-numbers a b)
(filtered-accumulate prime? + 0 identity a inc b))
(sum-prime-numbers 1 10)
(+ 1 2 3 5 7)
(define (gcd a b)
(if (= b 0)
a(gcd b (remainder a b))))
(define (product-prime-numbers-less-than n)
(define (prime-to x)
(= 1 (gcd x n)))
(filtered-accumulate prime-to * 1 identity 1 inc (- n 1)))
(product-prime-numbers-less-than 2)
(product-prime-numbers-less-than 3)
(product-prime-numbers-less-than 4)
(product-prime-numbers-less-than 5)
(product-prime-numbers-less-than 6)
(product-prime-numbers-less-than 7)
(product-prime-numbers-less-than 8)
(product-prime-numbers-less-than 9)
(product-prime-numbers-less-than 10)