SICP 연습문제 1.33 친절한 풀이

문제

거르개^filter라는 개념을 끌어들여, 연습문제 1.32에 나온 accumulate의 쓰임새를 더 넓혀 보자. 다시 말해, 정해진 넓이에 속하는 값 가운데 어떤 조건을 만족하는 값만 묶고 나머지는 걸러내는 accumulate를 만든다는 얘기다.이 프로시저를 filtered-accumulate라 한다. filtered-accumulate는 accumulate와 같은 인자를 받으며, 아울러 거르개로 쓸 술어 프로시저^predicate까지 받아야 한다. filtered-accumulate로 다음 문제의 답이 되는 식을 써 보라.

a. (prime? 프로시저가 벌서 있다 치고) a에서 b 사이에 있는 모든 소수^씨수를 제곱하여 더하는 식

b. n과 서로소인수, 즉 $i<n$이고 0보다 큰 정수 $i$가 $GCD(i,n)=1$이 되는, n보다 작고 0보다 큰 모든 정수를 곱하는 식

문제로 부터 얻은 것

프로시저를 인자로 받을 수 있다면, 함수형 프로그래밍에 가까운 언어사용을 할 수 있다.

문제풀이

filtered-accumulate 구현

기존의 accumulate에 filter를 추가해서 구현해 보겠습니다.
단순히 if문을 하나 더 추가시켜서 (fiter a)가 참이면, result에 결과를 축적하는 방식입니다.

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

a. a에서 b 사이에 있는 모든 소수를 제곱하여 더하는 식

prime? 프로시저는 아래와 같습니다.

(define (divides? a b)
  (= (remainder a b) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? n test-divisor) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

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

위 prime?을 기반으로 문제에서 요구하는 식을 구하면 아래와 같습니다.

(filtered-accumulate prime? + 0 square a inc b)

(inc는 1을 더하는 프로시저)

b. n보다 작은 서로소를 곱하는 식

GCD 프로시저는 아래와 같습니다.

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

위 GCD를 기반으로 문제에서 요구하는 식을 구하면 아래와 같습니다.

(define (disjoint? x)
  (= (gcd x n) 1))

(define (self x)
  x)

(filtered-accumulate disjoint? * 1 self 1 inc (- n 1))

위의 식 자체로는 n이 정의되지 않았기 때문에 실행할 수 없습니다.

읽어주셔서 감사합니다.