filtered-accumulate
函数比 练习 1.33 的 accumulate
函数多增加一个谓词函数参数 valid?
,用于确保在计算时只对符合条件的项进行累积:
;;; 33-filtered-accumulate.scm
(define (filtered-accumulate combine null-value term a next b valid?)
(if (> a b)
null-value
(let ((rest-terms (filtered-accumulate combine
null-value
term
(next a)
next
b
valid?)))
(if (valid? a)
(combine (term a) rest-terms)
rest-terms))))
使用 filtered-accumulate
定义 primes-sum
,它加起给定范围内的所有素数,其中素数检测函数 prime?
来自书本 33 页:
;;; 33-primes-sum.scm
(load "33-filtered-accumulate.scm")
(load "p33-prime.scm")
(define (primes-sum a b)
(filtered-accumulate +
0
(lambda (x) x)
a
(lambda (i) (+ i 1))
b
prime?))
测试:
1 ]=> (load "33-primes-sum.scm")
;Loading "33-primes-sum.scm"...
; Loading "33-filtered-accumulate.scm"... done
; Loading "p33-prime.scm"...
; Loading "p33-smallest-divisor.scm"...
; Loading "p33-divides.scm"... done
; Loading "p33-find-divisor.scm"... done
; ... done
; ... done
;... done
;Value: primes-sum
1 ]=> (primes-sum 1 10) ; 1 + 2 + 3 + 5 + 7 = 18
;Value: 18
根据题目给出的互素性质,使用 gcd
函数写出 coprime?
谓词,用于检查两个整数是否互素:
;;; 33-coprime.scm
(define (coprime? i n)
(and (< i n)
(= 1 (gcd i n))))
测试:
1 ]=> (load "33-coprime.scm")
;Loading "33-coprime.scm"... done
;Value: coprime?
1 ]=> (coprime? 2 7)
;Value: #t
1 ]=> (coprime? 2 4)
;Value: #f
然后将这个 coprime?
和 filtered-accumulate
组合起来,写成 product-of-coprimes
:
;;; 33-product-of-coprimes.scm
(load "33-coprime.scm")
(load "33-filtered-accumulate.scm")
(define (product-of-coprimes n)
(filtered-accumulate *
1
(lambda (x) x)
1
(lambda (i) (+ i 1))
n
(lambda (x) (coprime? x n))))
注意,因为 coprime?
函数需要两个参数,所以在 accumulate
函数的最后部分,使用了一个 lambda
表达式将参数 n
闭包进去,作为 coprime?
的第二个参数。
测试:
1 ]=> (load "33-product-of-coprimes.scm")
;Loading "33-product-of-coprimes.scm"...
; Loading "33-filtered-accumulate.scm"... done
; Loading "33-coprime.scm"... done
;... done
;Value: product-of-coprimes
1 ]=> (product-of-coprimes 10) ; 1 * 3 * 7 * 9 = 189
;Value: 189
;;; 33-iter-filtered-accumulate.scm
(define (filtered-accumulate combine null-value term a next b valid?)
(define (iter i result)
(cond ((> i b)
result)
((valid? i)
(iter (next i) (combine (term i) result)))
(else
(iter (next i) result))))
(iter a null-value))
测试:
1 ]=> (load "33-iter-filtered-accumulate.scm")
;Loading "33-iter-filtered-accumulate.scm"... done
;Value: filtered-accumulate
1 ]=> (filtered-accumulate + ; 2 + 4 + 6 + 8 + 10 = 30
0
(lambda (x) x)
1
(lambda (i) (+ i 1))
10
even?)
;Value: 30