Exercise1-32 <---> Exercise1-34
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:
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).
Scheme solution:
(define (filtered-accumulate combiner null-value term a next b predicate)
(define (iter a result)
(if (> a b)
result
(iter (next a)
(if (predicate a)
(combiner result (term a))
result))))
(iter a null-value))
(define (sum-prime-squares a b)
(filtered-accumulate + 0 (lambda (x) (* x x)) a 1+ b prime?))
(define (product-relative-primes n)
(define (relative-prime? x)
(= (gcd n x) 1))
(filtered-accumulate * 1 (lambda (x) x) 1 1+ n relative-prime?))
Haskell solution:
filtered'accumulate combiner null'value term a next b predicate = iter a null'value
where
iter a result | a > b = result
| otherwise = iter (next a)
(if predicate a then combiner result (term a)
else result)
sum'prime'squares a b = filtered'accumulate (+) 0 (\x -> x*x) a (1+) b is'prime
product'relative'primes n = filtered'accumulate (*) 1 id 1 (1+) n is'relative'prime
where is'relative'prime x = gcd n x == 1
OCaml solution:
let filtered_accumulate combiner null_value term a next b predicate =
let rec iter a result =
if a > b then
result
else
iter (next a)
(if predicate a then combiner result (term a)
else result)
in
iter a null_value
let sum_prime_squares a b = filtered_accumulate (+) 0 (fun x -> x*x) a succ b is_prime
let product_relative_primes n =
let is_relative_prime x = gcd n x = 1 in
filtered_accumulate ( * ) 1 (fun x -> x) 1 succ n is_relative_prime
Standard ML solution:
fun filtered_accumulate (combiner, null_value, term, a, next, b, predicate) = let
fun iter (a, result) =
if a > b then
result
else
iter (next a,
if predicate a then combiner (result, term a)
else result)
in
iter (a, null_value)
end
fun sum_prime_squares (a, b) = filtered_accumulate (op +, 0, fn x => x*x, a, fn x => x+1, b, is_prime)
fun product_relative_primes n = let
fun is_relative_prime x = gcd (n, x) = 1
in
filtered_accumulate (op *, 1, fn x => x, 1, fn x => x+1, n, is_relative_prime)
end
Exercise1-32 <---> Exercise1-34
Comments
| iterative solution is for losers | ||||
Posted by lal-99-212  at 2008-09-06 23:12:39
X
| ||||