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

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

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

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: 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プロジェクト (著), 川合 史朗 (監修), オライリージャパン)
• Scheme手習い

問題 1.33-a, b.

コード(BBEdit, Emacs)

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

(define square (lambda (x) (* x x)))
(define identity (lambda (x) x))
(define inc (lambda (n) (+ n 1)))
(define prime?
  (lambda (n)
    (and (> n 1) (= n (smallest-divisor n)))))
(define smallest-divisor
  (lambda (n) (find-divisor n 2)))
(define find-divisor
  (lambda (n test-divisor)
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor n (inc test-divisor))))))
(define divides? (lambda (a b) (= (remainder b a) 0)))

(define gcd
  (lambda (a b)
    (if (= b 0)
        a
        (gcd b (remainder a b)))))

(define filtered-accumulcate
  (lambda (pred combiner null-value term a next b)
    (define inner
      (lambda (x result)
        (cond ((> x b) result)
              ((pred x)
               (inner (next x)
                      (combiner (term x)
                                result)))
              (else (inner (next x) result)))))
    (inner null-value a)))

;; a.
(define prime-sum
  (lambda (a b)
    (filtered-accumulcate prime? + 0 identity a inc b)))

(print (prime-sum 0 10))                ; 2 + 3 + 5 + 7 = 17
(print (prime-sum 0 100))

(define relatively-prime-product
  (lambda (n)
    (filtered-accumulcate (lambda (x) (= (gcd x n) 1))
                          *
                          1
                          identity
                          1
                          inc
                          (- n 1))))

(print (relatively-prime-product 10))             ; 1 * 3 * 7 * 9 = 189
(print (relatively-prime-product 100))

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

$ ./sample33.scm
17
1060
189
426252881942771063138176712755660145456313428952105524817872601
$