SICP独習会 木の写像 (問題2.30〜)

問題2.30

高階手続きを使わない版

(define (square-tree tree)
  (cond
    ((null? tree) '())
    ((not (pair? tree)) (* tree tree))
    (else (cons (square-tree (car tree))
                (square-tree (cdr tree))))))

高階手続きを使う版

(define (square-tree tree)
  (map
    (lambda (sub-tree)
      (if (pair? sub-tree)
        (square-tree sub-tree)
        (* sub-tree sub-tree)))
    tree))

問題2.31

定義はすらすらっと書けた。

(define (square-tree tree)
  (tree-map (lambda (x) (* x x)) tree))

(define (tree-map proc tree)
  (map
    (lambda (sub-tree)
      (if (pair? sub-tree)
        (tree-map proc sub-tree)
        (proc sub-tree)))
    tree))

以下がtraceしてみた結果。

gosh> (square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)))

CALL square-tree (1 (2 (3 ...) 5) (6 7))

 CALL tree-map #[proc] (1 (2 (3 ...) 5) (6 7))

  CALL tree-map #[proc] (2 (3 4) 5)

   CALL tree-map #[proc] (3 4)

   RETN tree-map (9 16)

  RETN tree-map (4 (9 16) 25)

  CALL tree-map #[proc] (6 7)

  RETN tree-map (36 49)

 RETN tree-map (1 (4 (9 ...) 25) (36 49))

RETN square-tree (1 (4 (9 ...) 25) (36 49))

(1 (4 (9 16) 25) (36 49))

気付いたのだけれど、再帰してる手続きは後ろから結果ができていくみたいね。当たり前といえば、そうなのだけれど。