Scheme - データによる抽象の構築(階層データ構造と閉包性(階層構造(append, cons, list, 部分木の置く間d逆順にする手続き, 木の全ての葉)))

計算機プログラムの構造と解釈
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.2(階層構造)、問題 2.26, 2.27, 2.28.を解いてみる。

その他参考書籍

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

問題 2.26, 2.27, 2.28.

コード(BBEdit, Emacs)

sample.scm

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

(print "2.26")

(define x (list 1 2 3))

(define y (list 4 5 6))

(print (append x y)) ; (1 2 3 4 5 6)

(print (cons x y))   ; ((1 2 3) 4 5 6)

(print (list x y))   ; ((1 2 3) (4 5 6))

(print "2.27")
(define (reverse items)
  (define (iter a result)
    (if (null? a)
        result
        (iter (cdr a)
              (cons (car a)
                    result))))
  (iter items '()))

(define x (list (list 1 2) (list 3 4)))

(define (deep-reverse items)
  (define (iter items result)
    (if (null? items)
        result
        (iter (cdr items)
              ((lambda (item)
                 (cons (if (pair? item)
                           (deep-reverse item)
                           item)
                       result))
               (car items)))))
  (iter items '()))
                          
(print x)

(print (reverse x))

(print (deep-reverse x))

(print "2.28")

(define (fringe items)
  (define (iter items)
    (if (null? items)
        items
        ((lambda (item rest)
           (if (pair? item)
               (append (fringe item)
                       (fringe rest))
               (cons item
                     (fringe rest))))
         (car items) (cdr items))))
  (iter items))

(print (fringe x))

(print (fringe (list x x)))

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

$ ./sample.scm
2.26
(1 2 3 4 5 6)
((1 2 3) 4 5 6)
((1 2 3) (4 5 6))
2.27
((1 2) (3 4))
((3 4) (1 2))
((4 3) (2 1))
2.28
(1 2 3 4)
(1 2 3 4 1 2 3 4)
$