Scheme - 高階手続きによる抽象(引数としての手続き(filtered accumulate))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の1(手続きによる抽象の構築)、1.3(高階手続きによる抽象)、1.3.1(引数としての手続き)、問題 1.33-a, b.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 1.33-a, b.

a.は反復的プロセスで手続きを書いたので、今回は再帰的プロセスで。

コード(BBEdit, Emacs)

sample.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

(load "./compound_procedures.scm")

(define (filtered-accumulate combiner null-value term a next b predicate)
  (define (iter x result)
    (cond ((> x b) result)
          ((predicate x)
           (iter (next x)
                 (combiner (term x)
                           result)))
          (else (iter (next x)
                      result))))
  (iter a null-value))

;; a. 区間a, bの素数の二乗の和
(define (prime-square-sum a b)
  (filtered-accumulate + 0 square a inc b prime?))

;; b.
(define (gcd-sum n)
  (filtered-accumulate *
                       1
                       identity
                       1
                       inc
                       (- n 1)
                       (lambda (i)
                         (= (gcd i n)
                            1))))

;; テスト
(print "a.")
(for-each (lambda (x)
            (define a (car x))
            (define b (cadr x))
            (print "区間 [" a ", " b "]: " (prime-square-sum a b)))
          '((2 3) (2 4) (2 5) (2 6) (2 7)
            (5 6) (5 7) (5 8) (5 9) (5 10)))

(print "b.")
(for-each (lambda (n)
            (print "n = " n ": " (gcd-sum n)))
          '(2 3 4 5 6 7 8 9 10))

入出力結果(Terminal(gosh), REPL(Read, Eval, Print, Loop))

$ ./sample.scm 
a.
区間 [2, 3]: 13
区間 [2, 4]: 13
区間 [2, 5]: 38
区間 [2, 6]: 38
区間 [2, 7]: 87
区間 [5, 6]: 25
区間 [5, 7]: 74
区間 [5, 8]: 74
区間 [5, 9]: 74
区間 [5, 10]: 74
b.
n = 2: 1
n = 3: 2
n = 4: 3
n = 5: 24
n = 6: 5
n = 7: 720
n = 8: 105
n = 9: 2240
n = 10: 189
$