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

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

More than 1 year has passed since last update.

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