Posted at

SICP読書録 #26 練習問題2.33 - 練習問題2.36

hiroshi-manabe様の日本語訳を使わせてもらいます。

練習問題等はGaucheで実行。

前回はこちら


練習問題 2.33

accumulate手続きを用いてリスト操作を定義する。


_.scm

; 再掲

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

(define (map p sequence)
(accumulate (lambda (x y) (cons (p x) y)) nil sequence))

(define (append seq1 seq2)
(accumulate cons seq2 seq1))

(define (length sequence)
(accumulate (lambda (x y) (+ y 1)) 0 sequence))


実行結果。


_.scm

gosh> (map square '(1 2 3 4))

(1 4 9 16)
gosh> (append '(1 2) '(3 4))
(1 2 3 4)
gosh> (length '(1 2 3 4))
4


練習問題 2.34

ホーナー法というアルゴリズムによって評価すると、以下の多項式は

a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0

次の式と等価である。

(...(a_nx+a_{n-1})x+...+a_1)x+a_0

この式を評価する手続きを作ってみよう。


_.scm

(define (horner-eval x coefficient-sequence)

(accumulate
(lambda (this-coeff higher-terms)
(+ (* higher-terms x) this-coeff))
0 coefficient-sequence))

この手続きを用いて $x=2$ のときの $1+3x+5x^3+x^5$ を計算してみる。79になるはずだ。


_.scm

gosh> (horner-eval 2 '(1 3 0 5 0 1))

79


練習問題2.35

木の葉を数える手続き`count-leaves'を作ってみよう。


_.scm

(define (count-leaves t)

(accumulate + 0
(map (lambda (x)
(if (pair? x) (count-leaves x) 1)) t)))

実行結果。


_.scm

gosh> (count-leaves '(1 (2 3 (4 5 (6) 7) (8 9))))

9


練習問題 2.36

accumulate手続きの亜種としてaccumulate-nというのを作ってみよう。3つ目の引数として、リストのリストを受け取るというものだ。


_.scm

(define (accumulate-n op init seqs)

(if (null? (car seqs))
nil
(cons (accumulate op init (map car seqs))
(accumulate-n op init (map cdr seqs)))))

実行結果。


_.scm

gosh> (accumulate-n + 0 '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))

(22 26 30)