SICP Exercise 1.33: Filtered Accumulations

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:

1. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a prime? predicate already written)
2. 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).

The last exercise in section 1.3.1 is a simple extension of our work for exercise 1.32. We just need to modify the accumulate procedure so that it only accumulates the current term if the passed predicate indicates that it should be included. Now the implementation of accumulate we produced has two cases it deals with: either it's reached the end of the range we're iterating over, or we need to accumulate the term and iterate. To produce filtered-accumulate we need a third case: if the passed predicate indicates that the term derived from the value shouldn't be included then we should iterate without accumulating the term. To do this we need to change the if to a cond and add the new case:

(define (filtered-accumulate include? combiner null-value term a next b)
  (cond ((> a b) null-value)
        ((include? a) (combiner (term a)
                                (filtered-accumulate include?
                                                     combiner
                                                     null-value
                                                     term
                                                     (next a)
                                                     next
                                                     b)))
        (else (filtered-accumulate include?
                                   combiner
                                   null-value
                                   term
                                   (next a)
                                   next
                                   b))))

And we can do this iteratively as well:

(define (filtered-accumulate include? combiner null-value term a next b)
  (define (iter a result)
    (cond ((> a b) result)
          ((include? a) (iter (next a) (combiner (term a) result)))
          (else (iter (next a) result))))
  (iter a null-value))

Now lets put it into practice. Let's start with finding "the sum of the squares of the prime numbers in the interval a to b (assuming that you have a prime? predicate already written)". To do this we need to:

• Iterate through the interval a to b. To do this we can use inc as our next procedure.
• Filter the values iterated over to the prime numbers only. This is where we use the prime? predicate.
• Sum the squares of the filtered values. Here we can use the square procedure to produce the term and + as our combiner. As we're producing a sum our null-value should be 0.

Putting this all together we can produce the following procedure:

(define (sum-squares-of-primes a b)
  (filtered-accumulate prime? + 0 square a inc b))

Let's see what it gives us:

> (sum-squares-of-primes 1 10)
88
> (sum-squares-of-primes 5 15)
364

The final part of the exercise is to use filtered-accumulate to find "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)." Let's look again the components we need to put together:

• We need to iterate over all positive integers less than n. To do this we need to start at 1 and can use inc as our next procedure.
• To produce the filter predicate we need to check whether or not the value is relatively prime to n. Now we already have a gcd procedure from section 1.2.5, so we can use this in our predicate. All we need to do is calculate the GCD of the current value and n and check whether or not the value is 1. If it is then we have a relatively prime value and want to include it in the result.
• Finally, we're wanting to produce the product of all the values that pass the filter. So we need to use identity as the term, * as the combiner and 1 as the null-value.

Here's the finished procedure:

(define (product-of-relative-primes n)
  (define (relative-prime? x) (= (gcd x n) 1))
  (filtered-accumulate relative-prime? * 1 identity 1 inc n))

Let's see it in practice:

> (product-of-relative-primes 5)
24
> (product-of-relative-primes 9)
2240
> (product-of-relative-primes 16)
2027025