SICPを読む(54) 2.2.3(1) 公認インターフェイスとしての並び

Scheme

むむぅ。

  1. 引数としてリストを取り、奇数である葉の二乗の和を計算する
  2. 引数として数値を取り、偶数のフィボナッチ数列のリストを作る

プログラムを見てみよう。

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

(sum-odd-squares '(1 (2 3) (4 5)))
; 35

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

(even-fibs 20)
; (0 2 8 34 144 610 2584)

SICPでは「類似性がある」と説いている。

確かに似てはいるけど、引数が全然違うし、条件分岐が全然違う。返す値も全然違うじゃん!!

僕がこのふたつのプログラムを見たときに「類似性」を発見することは出来なかった。


SICPマジックを見ていきたいと思う。

まずは関数を揃えよう。

殆どsrfi-1があれば揃う。

実装してみる。

; map
(map square '(1 2 3 4 5)) ; (1 4 9 16 25)

; フィルタ
(define (filter predicate sequence)
  (cond ((null? sequence) sequence)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else
          (filter predicate (cdr sequence)))))

(filter odd? '(1 2 3 4 5)) ; (1 3 5)
(filter even? '(1 2 3 4 5)) ; (2 4)

; 畳み込み
(define (accumelate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumelate op initial (cdr sequence)))))

(accumelate + 0 '(1 2 3 4 5)) ; 15
(accumelate * 1 '(1 2 3 4 5)) ; 120
(accumelate cons '() '(1 2 3 4 5)) ; (1 2 3 4 5)
(fold-right cons '() '(1 2 3 4 5)) ; (1 2 3 4 5)
(accumelate string-append "" '("abc " "def " "ghi ")) ; abc def ghi
(fold-right string-append "" '("abc " "def " "ghi ")) ; abc def ghi

; リストを作る
(define (enumerate-interval low high)
  (if (> low high)
      '()
      (cons low (enumerate-interval (+ low 1) high))))

(enumerate-interval 5 10) ; (5 6 7 8 9 10)
(iota 6 5) ; (5 6 7 8 9 10)

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

(enumerate-tree '(1 (2 (3 (4) 5 6) 7 8) (9) 10)) ; (1 2 3 4 5 6 7 8 9 10)

map,filter,fold-right,iotaはsrfiにありますね。

enumerate-treeが見当たらず・・・treeに対するライブラリは少ないのかも。

道具が用意できたので

使ってみる。

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

(sum-odd-squares '(1 (2 3) (4 5))) ; 35

(define (even-fibs n)
  (accumelate cons '()
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))

(even-fibs 20) ; (0 2 8 34 144 610 2584)

おぉ。「類似性」が見えた!!

引数を受け取ったらenumerateをする。

enumerateでリストを作り、後はmapなりfilterなりお好きな加工をすればいい。

まとめると


とりあえずリストを作れ。


これだよこれ!!
Karetta|Gaucheプログラミング(立読み版)|「Lisp脳」の謎に迫る - Schemeプログラマの発想

「とりあえず1から100までのリストを作れば良さそうだ」

とりあえず得意フィールドに持ち込め。


これぞLisp脳。