SICP 연습문제 2.22 친절한 풀이

문제

Louis Reasoner는 연습문제 2.21에서 만든 square-list 프로시저가 반복 프로세스를 펼쳐낼 수 있도록 고쳐 쓰려고 한다.

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items nil))

한데, 위에 나온 대로 square-iter 프로시저를 정의해 보면, 원소 차례가 거꾸로 나온다. 왜 차례가 뒤집히는지 설명하라.
Louis는 cons에서 두 인자의 순서를 맞바꾸는 방법으로 이 오류를 풀어보려고 하였다.

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items nil))

허나, 이리 해보아도 제대로 된 결과가 나오지 않는다. 왜 그런가?

문제로 부터 얻은 것

반복 프로시저로 리스트를 거꾸로 반환하는 방법을 알 수 있었습니다.
리스트의 구조에 대해 다시 생각해 보는 기회였습니다.

문제풀이

1. 원소가 거꾸로 나오는 이유

연습문제 2.21에서 만든 square-list에서는 iter의 반환형이 (cons element iter)의 형태였습다.
즉, element를 리스트의 앞쪽에 두고 다음으로 연산한 결과들을 element의 뒤쪽에 iter로 붙이는 방식인 것입니다.

반면 이번 문제에서는 iter의 반환형이 (iter items-left answer)입니다.
iter가 다음 순서의 iter에게 물려주는 answer는 지금까지 계산한 결과물인 이전의 answer의 앞쪽에 element를 붙인 리스트입니다.
결국 element들은 answer의 앞쪽에 계속 붙게 되고, 순서가 뒤집어지는 것입니다.

2. 두 인자의 순서를 바꿔도 해결되지 않는 이유

책의 2.1.1절에서 설명한 리스트의 구조를 이해했다면, 왜 결과가 이상하게 나오는지 알 수 있습니다.
리스트의 기본 구조는 다음과 같습니다.

$list = (list \ element \ (anoter\_list))$

이것을 다른 말로 표현하면, 리스트의 모든 임의의 지점에서 항상 car는 원소 하나를 반환하고, cdr은 또다른 리스트를 반환한다는 말입니다. 리스트의 car에는 list가 아닌 element가 와야 프로시저가 정상적으로 동작합니다. 그러므로 리스트를 반환해야 하는 이전의 answer를 cons의 앞쪽 원소로 주게 되면 그 결과는 리스트로 표현되지 않습니다.

읽어주셔서 감사합니다.