SICP 연습문제 2.39 친절한 풀이

문제

연습문제 2.38에 나온 fold-right와 fold-left로 (연습문제 2.18에 나오는) reverse 프로시저의 정의를 마무리하라.

(define (reverse sequence)
  (fold-right (lambda (x y) <??>) nil sequence))
  
(define (reverse sequence)
  (fold-left (lambda (x y) <??>) nil sequence))

문제로 부터 얻은 것

fold-right와 left의 개념과 사용법을 조금 더 확장할 수 있었습니다.
right의 논리적인 실행순서는 가장 마지막 원소부터입니다.
left의 논리적인 실행 순서는 가장 처음의 원소부터입니다.

문제풀이

fold-right와 fold-left를 수식으로 나타내면 다음과 같습니다.
각 괄호 묶음은 op연산을 나타냅니다.

$right = (1 \ \ (2 \ \ (3 \ \ (4 \ \ (5 \ \ (6 \ \ (7 \ \ ⋯ \ \ initial)))))))$

$left = ((((((((initial \ \ 1)\ \ 2)\ \ 3)\ \ 4)\ \ 5)\ \ 6)\ \ 7)\ \ ⋯)$

a. fold-right

fold-right에서 람다식의 x는 지금 처리할 원소를 나타내고 y는 x와 묶을 나머지 차례열을 의미합니다. reverse는 원소들을 차례대로 뒤로 엮는 프로시저이므로 정답은 아래와 같습니다.

(define (reverse-1 sequence)
  (fold-right (lambda (x y) (append y (list x))) nil sequence))

b. fold-left

fold-left의 람다식은 right와 의미가 조금 다릅니다. x는 지금까지 처리한 원소들의 차례열을 나타내고 y는 새로운 원소를 나타냅니다. 그러므로 list의 데이터 형식에 맞추기 위해서는 아래와 같이 정의해야 합니다.

(define (reverse-2 sequence)
  (fold-left (lambda (x y) (cons y x)) nil sequence))

append 프로시저는 $Θ(n)$의 프로시저이고, cons는 $Θ(1)$의 프로시저입니다. reverse를 구현할 때는 append를 사용하는 fold-right보다 cons를 사용하는 fold-left가 효율적이라는 것도 알 수 있었습니다.

읽어주셔서 감사합니다.