SICP 연습문제 2.40 친절한 풀이

문제

정수 n을 인자로 받아서 $1 ≤ j ≤ i ≤ n$을 만족하는 $(i,j)$ 쌍의 차례열을 뽑아낼 수 있도록 unique-pairs 프로시저를 정의하라. 이 프로시저를 써서 prime-sum-pairs의 정의를 더 줄여 보아라.

문제로 부터 얻은 것

flatmap의 사용에 조금 더 익숙해졌습니다.
flatmap은 인자로 받은 프로시저가 각각의 원소에 적용되어 산출된 작은 리스트의 원소들을 밖으로 꺼내어 다시 합쳐진 리스트를 반환하는 프로시저입니다.

문제 풀이에 필요한 프로시저들

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))
  
(define (filter predicate seq)
  (cond ((null? seq) nil)
        ((predicate (car seq))
         (cons (car seq)
               (filter predicate (cdr seq))))
        (else (filter predicate (cdr seq)))))
    
(define (square x)
  (* x x))

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

문제풀이

a. unique-pair

문제 앞 절의 flatmap 설명을 이해했다면, 쌍으로 이루어진 리스트를 만들려고 할때 flatmap을 이용하면 편하다는 것을 떠올릴 수 있을 것입니다. 단순히 map 프로시저만 사용한다면, 하나의 i에 하나의 리스트밖에 만들어낼 수 없습니다. 하지만 flatmap을 이용하면 하나의 i에 대해 $(j,i)$쌍을 여러개 만들어서 이어붙일 수 있습니다.

(define (unique-pairs n)
  (flatmap (lambda (i)
             (map (lambda (j) (list i j))
                  (enumerate-interval 1 (- i 1))))
           (enumerate-interval 1 n)))

b. prime-sum-pairs

기존의 prime-sum-pairs를 이해했다면 어느 부분을 바꿔야 하는지는 쉽습니다.

(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))

(define (make-pair-sum pair)
  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (unique-pairs n))))

읽어주셔서 감사합니다.