Scheme - データによる抽象の構築(階層データ構造と閉包性(公認インターフェースとしての並び(並びの演算(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))の2(データによる抽象の構築)、2.2(階層データ構造と閉包性)、2.2.3(公認インターフェースとしての並び)、並びの演算、問題 2.38.を解いてみる。

その他参考書籍

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

問題 2.38.

コード(BBEdit, Emacs)

sample.scm

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

;; これまでに書いた手続き
(load "./procedures.scm")

(define fold-right accumulate)
;; fold-rightとfold-leftがどのような並びに大しても同じ値を生じる為には
;; opが結合律と可換律を満たす必要がある

(define items (list 1 2 3))

(for-each print
          (list
           ;; 除算は結合律、可換律共に満たさないので右畳み込みと左畳み込みで
           ;; 値が異なる
           (fold-right / 1 items)  ; 3/2
           (fold-left / 1 items)   ; 1/6
           ;; list手続きは結合律、可換律を満たさないので右畳み込みと左畳み込みで
           ;; 値は異なる
           (fold-right list nil items)  ; (1 (2 (3 ())))
           (fold-left list nil items)   ; (((() 1) 2) 3)
           ;; おまけ
           ;; +, *は結合律、可換律を共に満たすので、右多々見込みと左畳み込みの
           ;; 値は同じ
           (fold-right + 0 items)
           (fold-left + 0 items)
           (fold-right + 10 items)
           (fold-left + 10 items)
           (fold-right * 0 items)
           (fold-left * 0 items)
           (fold-right * 10 items)
           (fold-left * 10 items)))

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

$ ./sample.scm
3/2
1/6
(1 (2 (3 ())))
(((() 1) 2) 3)
6
6
16
16
0
0
60
60
$