SICP 연습문제 2.33 친절한 풀이

문제

아래는 accumulate를 이용해서 리스트 기본 연산을 몇 개 정의하려는 것이다. 그 중 빈 곳을 채워 보아라.

(define (map p sequence)
  (accumulate (lambda (x y) <??>) nil sequence))
  
(define (append seq1 seq2)
  (accumulate cons <??> <??>))
  
(define (length sequence)
  (accumulate <??> 0 sequence))

문제로 부터 얻은 것

차례열 연산의 핵심 부품인 accumulate 프로시저의 이해도를 높일 수 있었습니다.

문제풀이

이 문제를 풀기 위해서는 accumulate 프로시저를 제대로 이해하고 가야 합니다. 눈으로 읽고 이해했다고 완전히 이해한 것이 아닙니다. 책을 보지 않고 직접 손으로 코딩해 보면서 어떤 원리인지를 다시 한번 알고 가셨으면 좋겠습니다.

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

a. map

accumulate의 op 인자에는 인자를 두개 받는 프로시저를 넘겨야 합니다. map은 당장 처리해야 하는 원소 하나에 p를 적용시켜 cons로 묶어주는 프로시저이므로 (cons (p x) y)를 람다식으로 넣으면 됩니다.

(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y))
              nil
              sequence))

b. append

accumulate의 initial은 한글로 초기값이라는 뜻을 담고 있지만, 리스트의 막바지에 달했을 때 마지막 자리에 넣을 인자입니다. 그러므로 append의 순서를 맞추기 위해서는, seq2를 initial에 넣고, seq1을 sequence에 넣어야 합니다.

(define (append seq1 seq2)
  (accumulate cons seq2 seq1))

c. length

op 인자에 들어갈 람다식의 첫번째 원소가 무엇이든 간에 최종결과에 1을 더해주는 프로시저를 정의해야 합니다. 여기서 주목할 점은, (lambda (x y) (+ 1 y))라는 표현입니다. y 인자는 시퀸스의 나머지 부분에 op를 적용한 식이 자리잡게 됩니다. 표현이 어색해 보일 수 있으므로 찬찬히 생각해 보시기 바랍니다.

(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

d. 테스트 코드

읽어주셔서 감사합니다.