問題2.73 2.3.2 節の記号微分を行うプログラム。 (define (deriv exp var) (cond ((number? exp) 0) ((variable? exp) (if (same-variable? exp var) 1 0)) ((sum? exp) (make-sum (deriv (addend exp) var) (deriv (augend exp) var)…続きを読む

問題2.71 (define (expt-pair pairs) (let ((n (length pairs))) (define (iter pairs) (let ((i (- n (length pairs)))) (if (null? pairs) ‘() (cons (list (car pairs) (expt 2 i)) (iter (cdr pairs)))))) (iter p…続きを読む

問題2.70 (define rock-code ‘((A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3) (YIP 9) (WAH 1))) rock-code gosh> ((A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3) (YIP 9) (WAH 1)) (define rock-huffman-tre…続きを読む

問題2.69 対のリストとその順序づけられたリストが以下の場合… (make-leaf-set ‘((A 4) (B 2) (C 1) (D 1))) gosh> ((leaf D 1) (leaf C 1) (leaf B 2) (leaf A 4)) 次のような形で… 以下のような Huffman木 を生成する手続きを考える。 ((leaf A 4) ((leaf…続きを読む

問題2.68 記号が木に存在するかどうかを調べるには、ルートにある記号の集合のリストを最初に調べるとよい。 左部分木に記号が存在すれば左部分木をたどって行き、左部分木に無い場合は右部分木をたどって行く。 (define (encode-symbol symbol tree) (define (enc-iter tree) (if (leaf? tree) ‘() (if (memq symbol …続きを読む

問題2.67 (define sample-tree (make-code-tree (make-leaf ‘A 4) (make-code-tree (make-leaf ‘B 2) (make-code-tree (make-leaf ‘D 1) (make-leaf ‘C 1))))) (print sample-tree) gosh> ((leaf A 4) ((leaf B 2) …続きを読む

問題2.66 レコードの集合がキーの数値で順序づけられている二進木で構造化されている場合の lookup 手続き。 (define (key record) (car record)) (define (value record) (cadr record)) (define (make-record key value) (list key value)) (define (lookup giv…続きを読む

問題2.65 問題2.62等で作った、順序づけられたリストによる集合の union-set、intersection-set を利用する。 木構造データをリストに変換してから演算を行い、結果のリストを木構造データに変換する。 (define set1 ‘(1 2 3 4 5)) (define set2 ‘(2 4 6)) (define tree1 (list->tree set1)) ;…続きを読む

問題2.64a partial-tree はリストとその長さを引数として与えられ、長さからリストを半分に分ける。 中間の要素でエントリを、前のリストで左部分木を、後ろのリストで右部分木を作る。 結果は"エントリと左部分木と右部分木とで構成された木" と "木に含まれなかった要素から成るリスト" を cons したものを返す。 (define (list-&g…続きを読む

問題2.63a tree->list-1、tree->list-2 のどちらの手続きでも同じ結果となる。 (define (tree->list-1 tree) (if (null? tree) ‘() (append (tree->list-1 (left-branch tree)) (cons (entry tree) (tree->list-1 (right-b…続きを読む