Posted at

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

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

練習問題等はGaucheで実行。

前回はこちら


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

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


_.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)))))


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

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


_.scm

(define (list-fib-squares n)

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

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


_.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))))