Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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)
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away