SICP 연습문제 2.68 친절한 풀이

문제

encode 프로시저는 글과 나무를 인자로 받아서, 그 글을 인코딩한 비트 리스트를 내놓는다.

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
        (encode (cdr message) tree))))

인코딩 나무를 보고, 한 글자를 인코딩하여 비트 리스트를 내놓도록 encode-symbol 프로시저를 짜라. 그 글자가 나무에 없을 때에는 잘못되었음을 알려주도록 프로시저를 설계해야 한다. 이 프로시저가 올바로 돌아가는지 알아보기 위하여, 연습문제 2.67에서 sample-tree로 얻어낸 결과를 인코딩하여, 그 결과가 처음 글과 같은지 살펴보라.

문제로 부터 얻은 것

처음 푸는데 시간도 오래 걸렸고, 제 부족한 점을 많이 알았습니다.
첫째로 cons를 이용해서 (iter result) 없이 묶어야 좋은 프로시저라는 것을 알면서도 문제에 적용하지 못했습니다.
둘째로 tree의 고르개를 정확히 이해하지 못해서, symbols가 list를 반환하는줄 몰라서 많이 해맸습니다
셋째로 길을 찾는데 아주 유용한 고르개인 symbols를 제대로 활용하지 못했습니다.

문제풀이

저의 처음 아이디어는 이렇습니다. 가능성이 높은 코드일수록 left-branch에 있을 확률이 높으므로, 왼쪽 가지의 symbols를 검사해서 찾는 값이 있다면 왼쪽 가지에 iter를 적용합니다. 왼쪽에 찾는 결과가 없다면 오른쪽 가지에서 동일한 작업을 반복하는 것입니다. 그러다가 이파리에 다다르면 목표값인지 확인하고, 맞다면 경로를 반환하고 틀리다면 #f를 반환하면 됩니다.
memq 프로시저는 찾는 변수가 리스트 안에 있는지 알려주는 프로시저입니다.

(define (encode-symbol symbol tree)
  (define (iter current-tree result)
    (if (leaf? current-tree)
        (if (eq? (car (symbols current-tree)) symbol)
            result
            #f)
        (if (memq symbol (symbols (left-branch current-tree)))
            (iter (left-branch current-tree) (append result '(0)))
            (iter (right-branch current-tree) (append result '(1))))))
  (iter tree '()))

하지만 알시다시피 append로 묶는 것은 cons에 비해 비효율적입니다. 게다가 코드가 아름답지 않았습니다. 결국 인터넷에서 더 아름다운 해답을 찾았습니다. cons로 데이터를 묶고, 불필요한 eq?를 없앤 프로시저입니다.

(define (encode-symbol symbol tree)
  (if (leaf? tree)
      '()
      (let ((left (left-branch tree)))
        (if (memq symbol (symbols left))
            (cons 0 (encode-symbol symbol left))
            (cons 1 (encode-symbol symbol (right-branch tree)))))))

위의 프로시저를 cond를 사용해서 좀 더 아름답게 하면 다음과 같습니다.

(define (encode-symbol symbol tree) 
  (cond ((leaf? tree) '()) 
        ((memq symbol (symbols (left-branch tree))) 
         (cons 0 (encode-symbol symbol (left-branch tree)))) 
        ((memq symbol (symbols (right-branch tree))) 
         (cons 1 (encode-symbol symbol (right-branch tree)))) 
        (else (error "symbol not in tree" symbol)))) 

처음 푸는데 시간도 오래 걸렸고, 제 부족한 점을 많이 알았습니다.

첫째로 cons를 이용해서 (iter result) 없이 묶어야 좋은 프로시저라는 것을 알면서도 문제에 적용하지 못했습니다.

둘째로 tree의 고르개를 정확히 이해하지 못해서, symbols가 list를 반환하는줄 몰라서 많이 해맸습니다.

셋째로 길을 찾는데 아주 유용한 고르개인 symbols를 제대로 활용하지 못했습니다.

반성할 점이 많은 하루였습니다.

읽어주셔서 감사합니다.