sicp exercise 1.33

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

(define true  #t)
(define false #f)

(define (square num) (* num num))

(define (expmod base exp m)
    (cond ((= exp 0) 1)
          ((even? exp)
               (remainder (square (expmod base (/ exp 2) m)) m))
          (else
               (remainder (* base (expmod base (- exp 1) m)) m))))

(define (fermat-test n)
    (define (prime-impl n base)
        (= (expmod base n n) base))
   (prime-impl n (+ 1 (random (- n 1)))))

(define (prime-test n times)
   (cond ((= times 0) true)
   ((fermat-test n) (prime-test n (- times 1)))
   (else false)))

(define (prime? n) (prime-test n 10))


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

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

(define (sum-square-if-prime a b)
   (define (next x) (+ x 1))
   (filtered-accumulate-iter + prime? 0 square a next b))

(display (sum-square-if-prime 4 10)) (newline)