Looking Out To Sea

My latest interesting thought while doing the exercises in SICP is a bit confusing because the book is suggesting something which seems wrong. In Exercise 1.33, after creating a function accumulate (a kind of fold without lists where the start and end values are specified) it asks:

You can obtain an even more general version of accumulate 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.

The tricky bit I see is the “even more general version” instruction. As far as I can tell filtered-accumulate can be written in terms of accumulate. It’s not more general or more powerful than the plain accumulate.

The previously-defined accumulate takes the following arguments:

• a null-value and a combiner-function (which is to say the binary operator and identity for some monoid)
• a pair of numbers representing the start and end value in the range we want to accumulate over
• a function which maps values in this range to values in the monoid described above (and it could be the identity)
• a function to get to the next value in the range given the current one

My (recursive) accumulate looks like this:

(define (accumulate combiner null-value term a next b)
  (if (> a b)
    null-value
    (combiner (term a) (accumulate combiner null-value term (next a) next b))))

Exercise 1.33 wants you to pre-filter values so that they don’t all get added together. Only those a which pass some predicate get combined into the result. But since the combining function comes specified with a null value it’s not necessary to skip over undesired results. All we need to do is convert any values which fail the test into the null value.

Put it this way: given a list of numbers between one and ten, you could find the sum of primes by either removing all the non-primes, or converting them into zeroes, because adding zero doesn’t affect the result. Similarly if you want the product of odd numbers between 14 and 103 you can filter out all the even numbers or turn them into 1s, because multiplying by 1 doesn’t affect the end result.

And it just so happens that there is already a way in accumulate to convert numbers before they are combined together, the term argument. This is used to square input values or apply some other function. The key argument is that this function can check if the input meets some criterion and then either process it further or replace it with null-value.

(define (filtered-accumulate filter combiner null-value term a next b)
  (define (filterterm n) (if (filter n) (term n) null-value))
  (accumulate combiner null-value filterterm a next b))

All the solutions to this exercise that I have seen online basically re-implement the rest of accumulate with extra filtering. This doesn’t seem to be necessary. My implementation above works for the following two exercises (sum of squares of primes, and product of all relatively prime integers).

But the exercise plainly says that filter-accumulate is “an even more general version of accumulate”, which to my mind means that filter-accumulate should be able to produce answers which standard accumulate cannot. (And that filter-accumulate cannot be implemented in terms of accumulate.) What is the counter-example that I’m missing, or is the book wrong?

Note: I’ve starting putting my solutions for the SICP exercises online, at http://www.dougalstanton.net/code/sicp/.

Trackback URI | Comments RSS