# Filtered-Accumulate

Given the following task:

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).

I wrote this code:

(Utility functions)

(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))

(define (square x) (* x x))
(define (divisible? b a) (= (remainder b a) 0))
(define (smallest-divisor n)
(find-divisor n 2))
(define (find-divisor n test-divisor)
(define (next x)
(if (= x 2) 3 (+ x 2)))
(cond ((> (square test-divisor) n) n)
((divisible? n test-divisor) test-divisor)
(else (find-divisor n (next test-divisor)))))

(define (prime? x) (= (smallest-divisor x) x))

(define (inc x) (+ x 1))
(define (identity x) x)


Recursive:

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


Iterative:

(define (i-filtered-accumulate combiner filter null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner result (if (filter a) (term a) null-value)))))
(iter a null-value))


Sum of primes between a and b:

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


Product of relative primes less than n:

(define (product-of-relative-primes-less-than n)
(define (relprime-n i) (= (gcd i n) 1))
(filtered-accumulate * relprime-n 1 identity 1 inc n))


What do you think?

• idk if you consider it contrary to this exercises purpose, or maybe efficiency is it a premium, but you might consider just writing a standalone filter function and composing them. filter is a worthwhile function in its own write Apr 1, 2011 at 0:26

Since you're recursing only on a and possibly result, you can use an inner define that only changes these arguments.

When an item matches a filter condition, you can ignore it by recursing on the remaining items. You need not give it a null-value result. Putting these ideas together, we get:

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

(define (i-filtered-accumulate combiner filter? null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (if (filter? a) (combiner (term a) result) result))))
(iter a null-value))


The problem asks for a sum of square of primes, like so (note the negated filter):

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


You can check for relative primes starting with 2:

(define (product-of-relative-primes-less-than n)
(define (relative-prime-n? i) (= (gcd i n) 1))
(i-filtered-accumulate * relative-prime-n? 1 identity 2 inc n))


There are a few ways to address this

1. Write a filter-accumulate function like you are working on

2. Have seperate filter and accumulate functions and compose them (filter first)

3. Just use accumulate and work the filtering into your combine function (treat term like identity element when conditions not met). Consider 'automating' this with a function that takes filter and combine functions and puts them together.

example of third method for (a)

(accumulate (lambda (x y) (if (prime? b)
(a)
(+ a (square b))))
(range A B)
0)


'Accumulate' is usually called 'foldl'. So, your function is just

foldl f v $filter g xs  in Haskell. Also, your algorithm is quite inefficent. If I was to find prime numbers, I would sieve them with prime divisors below the square root of current number. Here is an example: primes = (2 :)$ flip filter [3..] $\n -> flip all (flip takeWhile primes$ \i -> i * i <= n) $\x -> n mod x /= 0 main = print$ take 10 \$ primes


Result:

[2,3,5,7,11,13,17,19,23,29]