SICP 연습문제 2.38 친절한 풀이

문제

accumulate 프로시저는 첫 번째 원소와 나머지 원소의 계산 결과를 오른쪽으로 엮어가면서 계산하기 때문에 fold-right라고도 한다. 이와 비슷한 연산으로 fold-left가 있는데 이것은 원소를 엮어가며 계산하는 방향이 fold-right의 반대다.

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

다음 식을 계산하면 어떤 결과가 나오는가?

(fold-right / 1 (list 1 2 3))
(fold-left / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left list nil (list 1 2 3))

한 차례열을 fold-right한 결과와 fold-left한 결과가 같으려면, op가 어떤 성질을 갖추어야 하는가?

문제로 부터 얻은 것

차례열을 순서대로 처리해서 묶는 방법에는 두가지가 있습니다.
하나는 왼쪽으로 묶는 방식이고 다른 하나는 오른쪽으로 묶는 방식입니다.
추상적으로 알고 있었던 두 방식의 차이를 확실히 알 수 있었습니다.

문제풀이

쉬운 이해를 위해 accumulate 프로시저를 가져오겠습니다.
accumulate 프로시저는 fold-right와 같은 말입니다.

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

위의 두 프로시저로 이해한 fold-right와 fold-left를 수식으로 나타내면 다음과 같습니다.
각 괄호 묶음은 op연산을 나타냅니다.

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

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

문제에서 주어진 테스트 코드를 한번 실행시켜 보겠습니다.

fold-left와 fold-right의 결과가 같기 위해서 op가 갖추어야 하는 성질을 생각해보겠습니다. 두 프로시저의 결과가 같은 예시를 하나 떠올려 보겠습니다. 제 머리속에 바로 떠오른 예시는 +입니다. op자리에 +를 넣는다면, left나 right방식 모두 인자로 받은 리스트의 합을 반환할 것입니다. +처럼 적용 순서에 영향을 받지 않는 프로시저들은 다들 똑같은 효과를 볼 것입니다. 그 예시로 곱셈도 계산 순서에 상관 없기 때문에 영향을 받지 않을 것입니다.

읽어주셔서 감사합니다.