Scheme - 階層データ構造と閉包(listを引数とする手続き(append, cons, list)、deep-reverse、fringe)

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

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の2(データによる抽象の構築)、2.2(階層データ構造と閉包)、2.2.2(階層構造)の問題 2.26、問題 2.27、問題 2.28を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 2.26

印字する結果。

(1 2 3 4 5 6)

((1 2 3) 4 5 6)

((1 2 3) (4 5 6)

確認。

コード

sample.scm

(define x (list 1 2 3))

(define y (list 4 5 6))

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

1 ]=> (append x y)

;Value 2: (1 2 3 4 5 6)

1 ]=> (cons x y)

;Value 3: ((1 2 3) 4 5 6)

1 ]=> (list x y)

;Value 4: ((1 2 3) (4 5 6))

問題 2.27

コード

sample.scm

(define (reverse items)
  (define (iter items result)
    (if (null? items)
        result
        (iter (cdr items) (append (list (car items)) result))))
  (iter items (list)))

(define (deep-reverse items)
  (define (iter items result)
    (cond ((null? items) result)
          ((pair? (car items)) (iter (cdr items) 
                                     (append (list (reverse (car items)))
                                             result)))
          (else (iter (cdr items) (append (list (car items)) 
                                          result)))))
  (iter items (list)))

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

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

1 ]=> x        

;Value 2: ((1 2) (3 4))

1 ]=> (reverse x)

;Value 3: ((3 4) (1 2))

1 ]=> (deep-reverse x)

;Value 4: ((4 3) (2 1))

問題 2.28

コード

sample.scm

(define (fringe items)
  (define (iter items result)
    (cond ((null? items) result)
          ((pair? (car items)) (iter (append (iter (car items) (list))
                                             (cdr items))
                                     result))
          (else (iter (cdr items)
                      (append result 
                             (list (car items)))))))
  (iter items (list)))

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

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

1 ]=> (fringe x)

;Value 2: (1 2 3 4)

1 ]=> (fringe (list x x))

;Value 3: (1 2 3 4 1 2 3 4)

1 ]=> x

;Value 4: ((1 2) (3 4))