開発環境
- 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.3(公認インターフェースとしての並び)の問題 2.33、問題 2.34、問題 2.35、問題 2.36、問題 2.37、問題 2.38、問題 2.39を解いてみる。
その他参考書籍
問題 2.33
コード
sample.scm
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (map p sequence)
(accumulate (lambda (x y)
(cons (p x) y))
(list)
sequence))
(define (append seq1 seq2)
(accumulate cons seq2 seq1))
(define (length sequence)
(accumulate (lambda (x y)
(+ 1 y))
0
sequence))
(define sequence-1 (list 1 2 3 4 5))
(define sequence-2 (list 6 7 8 9 0))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (map square sequence-1) ;Value 4: (1 4 9 16 25) 1 ]=> (append sequence-1 sequence-2) ;Value 5: (1 2 3 4 5 6 7 8 9 0) 1 ]=> (length sequence-1) ;Value: 5
問題 2.34
コード
sample.scm
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (horner-eval x coefficient-sequence)
(accumulate (lambda (this-coeff higher-terms)
(+ this-coeff (* higher-terms x)))
0
coefficient-sequence))
(horner-eval 2 (list 1 3 0 5 0 1))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (horner-eval 2 (list 1 3 0 5 0 1)) ;Value: 79
問題 2.35
コード
sample.scm
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (count-leaves t)
(accumulate + 0 (map (lambda (x)
(if (pair? x)
(count-leaves x)
1))
t)))
(define tree (list (list 1 2) 3 4))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (count-leaves tree) ;Value: 4 1 ]=> (count-leaves (list 1 (list 2 (list 3 4)))) ;Value: 4
問題 2.36
コード
sample.scm
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (accumulate-n op init seqs)
(if (null? (car seqs))
(list)
(cons (accumulate op init (map car seqs))
(accumulate-n op init (map cdr seqs)))))
(define s (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (accumulate-n + 0 s) ;Value 2: (22 26 30)
問題 2.37
コード
sample.scm
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (accumulate-n op init seqs)
(if (null? (car seqs))
(list)
(cons (accumulate op init (map car seqs))
(accumulate-n op init (map cdr seqs)))))
(define (dot-product v w)
(accumulate + 0 (map * v w)))
(define (matrix-*-vector m v)
(map (lambda (x) (dot-product x v))
m))
(define (transpose mat)
(accumulate-n cons
(list)
mat))
(define (matrix-*-matrix m n)
(let ((cols (transpose n)))
(map dot-product cols m)))
(define v (list 1 2 3 4))
(define w (list 4 5 6 6))
(define x (list 6 7 8 9))
(define m (list v w x))
(define n (list (list 1 2 3)
(list 4 5 6)
(list 7 8 9)
(list 2 3 4)))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (matrix-*-vector m v) ;Value 2: (30 56 80) 1 ]=> (transpose m) ;Value 3: ((1 4 6) (2 5 7) (3 6 8) (4 6 9)) 1 ]=> (transpose n) ;Value 4: ((1 4 7 2) (2 5 8 3) (3 6 9 4)) 1 ]=> (matrix-*-matrix m n) ;Value 5: (38 99 168)
問題 2.38
置き換えモデルで考えてみる。
(fold-right / 1 (list 1 2 3)) (/ 1 (fold-right / 1 (list 2 3))) (/ 1 (/ 2 (fold-right / 1 (list 3)))) (/ 1 (/ 2 (/ 3 1))) (/ 1 (/ 2 3)) (/ 1 2/3) 3/2 (fold-left / 1 (list 1 2 3)) (iter (/ 1 1) (list 2 3)) (iter 1 (list 2 3)) (iter (/ 1 2) (list 3)) (iter 1/2 (list 3)) (/ 1/2 3) 1/6 (fold-right list (list) (list 1 2 3)) (list 1 (fold-right list (list) (list 2 3))) (list 1 (list 2 (fold-right list (list) (list 3)))) (list 1 (list 2 (list 3 (list)))) (1 (2 (3 ()))) (fold-left list (list) (list 1 2 3)) (iter (list (list) 1) (list 2 3)) (iter (list (list (list) 1) 2) (list 3)) (list (list (list (list) 1) 2) 3) (((() 1) 2) 3)
確認。
コード
sample.scm
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (fold-left op initial sequence)
(define (iter result rest)
(if (null? rest)
result
(iter (op result (car rest))
(cdr rest))))
(iter initial sequence))
(define fold-right accumulate)
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (fold-right / 1 (list 1 2 3)) ;Value: 3/2 1 ]=> (fold-left / 1 (list 1 2 3)) ;Value: 1/6 1 ]=> (fold-right list (list) (list 1 2 3)) ;Value 2: (1 (2 (3 ()))) 1 ]=> (fold-left list (list) (list 1 2 3)) ;Value 3: (((() 1) 2) 3)
fold-rightとfold-leftが、どのようなならびに大しても同じ値を生じるためにopが満たすべき性質は、可換であること。+や*は満たす。-や/は満たさないことを確認。(/については上記で確認済。)
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (fold-right + 0 (list 1 2 3)) ;Value: 6 1 ]=> (fold-left + 0 (list 1 2 3)) ;Value: 6 1 ]=> (fold-right - 0 (list 1 2 3)) ;Value: 2 1 ]=> (fold-left - 0 (list 1 2 3)) ;Value: -6 1 ]=> (fold-right * 1 (list 1 2 3)) ;Value: 6 1 ]=> (fold-left * 1 (list 1 2 3)) ;Value: 6
問題 2.39
コード
sample.scm
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (fold-left op initial sequence)
(define (iter result rest)
(if (null? rest)
result
(iter (op result (car rest))
(cdr rest))))
(iter initial sequence))
(define fold-right accumulate)
(define (reverse-1 sequence)
(fold-right (lambda (x y)
(append y (list x)))
(list)
sequence))
(define (reverse-2 sequence)
(fold-left (lambda (x y)
(cons y x))
(list)
sequence))
(define x (list 1 2 3 4 5))
入出力結果(Terminal, REPL(Read, Eval, Print, Loop))
1 ]=> (reverse-1 x) ;Value 2: (5 4 3 2 1) 1 ]=> (reverse-2 x) ;Value 3: (5 4 3 2 1)
0 コメント:
コメントを投稿