SICP読書録 #25 2.2.3 標準インターフェイスとしての列

hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。

前回はこちら

2.2.3 標準インターフェイスとしての列

突然だけど、木構造を受け取り、含まれる奇数値の２乗の和を返す手続きはこうなる。

_.scm

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares (car tree))
                 (sum-odd-squares (cdr tree))))))

引数nで指定した数だけフィボナッチ数列を生成し、偶数のもののリストを返す手続きはこう。

_.scm

(define (even-fibs n)
  (define (next k)
    (if (> k n)
        nil
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ k 1))))))
  (next 0))

さて、上記2つの手続きは誰が何と言おうと「似ている」。どちらも次のことを行なっているのだ。

• (列挙) 木の葉を列挙し / フィボナッチ数を列挙し
• (フィルタ) 奇数を選び / 偶数を選び
• (変換) 2乗して / 値をそのまま
• (集積) 和を求める / リストにする

この、列挙、フィルタ、マップ、集積というパターンに基づいて、この手続きを作り直してみよう。

列の演算

まずは、リストに対して任意のフィルタをかける手続きを作ろう。

_.scm

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

動かしてみる。

_.scm

gosh> (filter odd? (list 1 2 3 4 5))
(1 3 5)

次は、集積を行う手続きだ。

_.scm

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

動かしてみる。

_.scm

gosh> (accumulate + 0 '(1 2 3 4 5))
15
gosh> (accumulate cons nil '(1 2 3))
(1 2 3)

残るは、列挙。

指定した範囲の整数リストを返す手続き。

_.scm

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))

木の葉を列挙する手続き。

_.scm

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))

それぞれ動かしてみる。

_.scm

gosh> (enumerate-interval 2 7)
(2 3 4 5 6 7)
gosh> (enumerate-tree '(1 (2 (3 4)) 5))
(1 2 3 4 5)

これで部品は完成した。先の手続きをそれぞれ作り直してみよう。

_.scm

(define (sum-odd-squares tree)
  (accumulate + 0 (map square (filter odd? (enumerate-tree tree)))))

(define (even-fibs n)
  (accumulate cons nil (filter even? (map fib (enumerate-interval 0 n)))))

まるで積み木を組み合わせるかのようにして実装できた。この方法だと、本来は複雑な手続きを簡単に作れる。

例えば、フィボナッチ数の２乗のリストが欲しい、となればこうだ。

_.scm

(define (list-fib-squares n)
  (accumulate cons nil (map square (map fib (enumerate-interval 0 n)))))

指定したリスト内の奇数の２乗の積が欲しい、のならばこう。

_.scm

(define (product-of-squares-of-odd-elements sequence)
  (accumulate * 1 (map square (filter odd? sequence))))

それぞれ動かしてみよう。

_.scm

gosh> (list-fib-squares 10)
(0 1 1 4 9 25 64 169 441 1156 3025)
gosh> (product-of-squares-of-odd-elements '(1 2 3 4 5))
225

社員マスタからプログラマだけを抽出し、最も給料が高いのは誰か？という手続きにだって応用できる。

_.scm

(define (salary-of-highest-paid-programmer records)
  (accumulate max 0 (map salary (filter programmer? records))))