Scheme - データによる抽象の構築(階層データ構造と閉包性(並びの表現(リストの写像(リストとcons))))

計算機プログラムの構造と解釈
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.1(並びの表現)、リストの写像、問題 2.22.、問題 2.23.を解いてみる。

その他参考書籍

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

問題 2.22.

リストを(list 1 2 3 4 5)とする。

逆順のリストをを作る場合の置き換えモデルは

(iter (list 1 2 3 4 5) nil)

(iter (list 2 3 4 5)
      (cons 1 nil))

(iter (list 3 4 5)
      (cons 4 (cons 1 nil)))

(iter (list 4 5)
      (cons 9 (cons 4 (cons 1 nil))))

(iter (list 5)
      (cons 16 (cons 9 (cons 4 (cons 1 nil)))))

(iter nil
      (cons 25 (cons 16 (cons 9 (cons 4 (cons 1 nil))))))

(cons 25 (cons 16 (cons 9 (cons 4 (cons 1 nil)))))

(25 16 9 4 1)

となる。

確認。

コード(BBEdit, Emacs)

sample.scm

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

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

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items nil))

(print (square-list (list 1 2 3 4 5)))

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

$ ./sample.scm
(25 16 9 4 1)
$

consの引数を交換した場合の置き換えモデルは

(iter (list 1 2 3 4 5) nil)

(iter (list 2 3 4 5)
      (cons nil
            1))

(iter (list 3 4 5)
      (cons (cons nil 1) 
            4))

(iter (list 4 5)
      (cons (cons (cons nil 1) 4)
            9))

(iter (list 5)
      (cons (cons (cons (cons nil 1) 4) 9)
            16))

(iter nil
      (cons (cons (cons (cons (cons nil 1) 4) 9) 16)
            25))

(cons (cons (cons (cons (cons nil 1) 4) 9) 16) 25)

(((((() . 1) . 4) . 9) . 16) . 25)

となる。

コード(BBEdit, Emacs)

sample.scm

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

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

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items nil))

(print (square-list (list 1 2 3 4 5)))

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

$ ./sample.scm
(((((() . 1) . 4) . 9) . 16) . 25)
$

問題 2.23.

コード(BBEdit, Emacs)

sample.scm

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

(define (for-each proc items)
  (cond ((null? items) #t)
        (else (proc (car items))
              (for-each proc (cdr items)))))

(print (for-each (lambda (x)
                   (newline) (display x))
                 (list 57 321 88)))

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

$ ./sample.scm

57
321
88#t
$