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)