問題回答

問2.27

(define (deep-reverse items)
  (define (iter items ret)
    (if (null? items)
        ret
        (iter (cdr items) (cons (reverse (car items)) ret))))

  (iter (cdr items) (cons (reverse (car items)) ())))

(define x (list (list 1 2) (list 3 4)))
(deep-reverse x)

問2.28

(define (fringe items)
  (define (iter items ret)
    (display items)(newline)
    (cond ((not (pair? items)) (append ret (list items)))
          ((null? (cdr items)) (append ret (iter (car items) ())))
          (else (append ret (iter (car items) ()) (iter (cdr items) ())))))

  (iter items ()))

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

問2.29
a.

(define (make-mobil left right)
  (list left right))

(define (make-branch length structure)
  (list length structure))

(define (left-branch mobil)
  (car mobil))

(define (right-branch mobil)
  (cadr mobil))

(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (cadr branch))


(define m (make-mobil (make-branch 1 ()) (make-branch 3 ())))
(left-branch m)
(right-branch m)

(branch-length (left-branch m))
(branch-structure (left-branch m))

b.

(define (total-weight mobil)
  (define (iter branch)
    (cond ((null? branch) 0)
          ((pair? branch) (+ (iter (left-branch branch)) (iter (right-branch branch))))
          (branch-structure branch)))

  (iter mobil))

(total-weight m)

c.

(define (balanced? mobil)
  (let ((lb (left-branch mobil))
        (rb (right-branch mobil)))
    (if (= (* (total-weight lb) (branch-length lb))
           (* (total-weight rb) (branch-length rb)))
        (begin (display "balanced")(newline))
        (begin (display "unbalanced")(newline)))))

(define m (make-mobil (make-branch 1 ()) (make-branch 3 ())))
(balanced? m)
(define m (make-mobil (make-branch 1 ()) (make-branch 1 ())))
(balanced? m)

d.
枝と、枝の部品の選択肢を修正すれば対応可

(define (left-branch mobil)
  (car mobil))

(define (right-branch mobil)
  (cdr mobil))

(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (cdr branch))

本文

木の写像
list に対するのと同様、再帰と一緒になった map を使用する

問題回答

問2.30

(define (square-tree items)
  (cond ((null? items) ())
        ((not (pair? items)) (* items items))
        (else (cons (square-tree (car items))
                    (square-tree (cdr items))))))

(square-tree (list 1
                   (list 2 (list 3 4) 5)
                   (list 6 7)))

map 版

(define (square-tree tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (square-tree sub-tree)
             (* sub-tree sub-tree)))
       tree))

(square-tree (list 1
                   (list 2 (list 3 4) 5)
                   (list 6 7)))

問2.31

(define (tree-map tree f)
  (map (lambda (sub-tree)
           (if (pair? sub-tree)
               (tree-map sub-tree f)
               (f sub-tree)))
       tree))

(define (square x) (* x x))

(define (square-tree tree)
  (tree-map tree square ))

(square-tree (list 1
                   (list 2 (list 3 4) 5)
                   (list 6 7)))

本文

2.2.2 階層構造

問題解答

問2.24
図を載せるのは割愛。

問2.25

(define v (list 1 3 (list 5 7) 9))
(car (cdr (car (cdr (cdr v)))))

(define v (list (list 7)))
(car (car v))

(define v (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr v))))))))))))

解答を見るとこんな感じだった。

(cadadr (cadadr (cadadr v)))

このあたり、ちょっとググるとゲシュタルト崩壊を起こしそうな解説が、、、、

問2.26
まずは挙動を予想。

(append x y) → (1 2 3 4 5 6)
(cons x y) → ((123) (456))
(list x y) → ((123) (456))

gosh> (append x y)
(1 2 3 4 5 6)
gosh> (cons x y)
((1 2 3) 4 5 6)
gosh> (list x y)
((1 2 3) (4 5 6))

cons を間違えていました。cons と list がきちんと分けて考えられていなかったっぽいです。

問題解答

問2.20

(define (same-party x . y)
  (define (iter f l)
    (cond ((null? l) ())
          ((= (mod (car l) 2) f) (cons (car l) (iter f (cdr l))))
          (else (iter f (cdr l)))))
  (iter (mod x 2) y))

(same-party 1 2 3 4 5 6 7)
(same-party 2 2 3 4 5 6 7)

終了条件をどうすればいいのかわからなくて、ちょっと考えてしまいました。
これくらいのプログラムを書くにも未だに慣れないです。

本文

リストの写像

map を使用して、より抽象化することができる

(define (map proc items)
  (if (null? items)
      ()
      (cons (proc (car items))
            (map proc (cdr items)))))

(map (lambda(x) (* x x))
     (list 1 2 3 4))

問題解答

問2.21

(define (square-list items)
  (if (null? items)
      ()
      (cons (* (car items) (car items))
            (square-list (cdr items)))))

(define (square-list items)
  (map (lambda(x) (* x x)) items))

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

問2.22
最初のコードは頭から値を取り出して、リストの頭に値を挿入しているので逆になってしまう。
変更したコードは、answer が対なので、対と値の対を作ってしまう。そのため、((() 1) 4 9) のような結果になってしまう。

問2.23

(define (for-each f items)
  (if (null? items)
      true
      (f (car items)) (for-each f (cdr items))))

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

これはこれで正解ですが、解答例を見ると begin というものがあるのですね。

4.7 順次実行

本日はここまで。

MIT OCW のビデオは完全に先を行ってしまったっぽいので当分お休みして、追いつくまでは本文に集中します。

本文

2.2 階層データ構造と閉包性
ある集合の要素にある演算を作用させて得られた要素が、またその集合の要素だった場合に、要素の集合はその演算のもとで閉じているというのが本来の閉包の定義

対の car 部分に値、 cdr 部分に次の対へのポインタを格納することでリスト構造を表現する。
また、このための手続きとして list がある。

※Gauche の場合、nil は ()
註釈を見ると、nil の扱いはかなり議論の的になったようで、嗚呼、乙。。。という感じ。

リスト演算

問題解答

問 2.17

(define odds (list 1 3 5 7 9))

(define (last-pair items)
  (if (null? (cdr items))
      (car items)
      (last-pair (cdr items))))

(last-pair odds)

問2.18

(define (reverse items)
  (define (reverse-iter items ret)
    (if (null? items)
        ret
        (reverse-iter (cdr items) (cons (car items) ret))))

  (reverse-iter (cdr items) (cons (car items) ())))

(define odds (list 1 3 5 7 9))

(reverse odds)

問2.19

(define (first-denomination coin-values)
  (car coin-values))

(define (except-first-denomination coin-values)
  (cdr coin-values))

(define (no-more? coin-values)
  (null? coin-values))

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(cc 100 us-coins)
(cc 100 uk-coins)

あまり深く考えずにペロッと書いたら正解っぽくなってしまってむしろキョドってしまった(汗

MIT OCW

Lecture 3A | MIT 6.001
本日の MIT ビデオは 2A の後半。

• cons/car/cdr を使用してリストを作成する方法
• 上記の糖衣構文、 list
• map

list や map は本ではまだ出てきていないのでここで初お目見え。
やってることはわかるけど、list すらプリミティブなデータ型として用意しないとは、、、、どんだけミニマム主義なんだ(汗

問題解答

問2.13
うーんという感じだったのでカンニング。何のことはない、手を動かすだけの問題だった。

m0↓ = c0 – (c0*p0), m0↑ = c0 + (c0*p0)
m1↓ = c1 – (c1*p1), m1↑ = c1 + (c1*p1)

m0*m1 の結果を v とすると、m0,m1 ともに正なので

v↓ = (c0 – (c0*p0))(c1 – (c1*p1))
v↑ = (c0 + (c0*p0))(c1 + (c1*p1))

v↓ = c0*c1 – c0(c1*p1) – c1(c0*p0) + (c0*p0)(c1*p1)
= c0*c1 – c0(c1*p1) – c1(c0*p0) + c0*c1*p0*p1

p0,p1 が小さいのでこの二つを掛けた値はゼロとみなす。

= c0*c1 – c0(c1*p1) – c1(c0*p0)
= c0c1(1-(p1+p0))

よって、誤差は p1+p0 になる。v↑も同様な手順で計算できる。

問題2.14
2.13 で求めた式を使って二つの式を計算してみると、同じになる。あれ?
これは、区間を意識する必要がありそう。。。。。と思って手計算してみたけど埒があかないのでカンニング。

どうやら、代数的に等価なのにプログラムに落とし込むと結果が異なるということがあるらしい。
この一連の問題はちょっと手に負えなさそう。ただ、扱う問題によってはここら辺はかなり大事な内容な気がするので、きちんと時間をかけて手を動かして理解した方がよさそう。

問題2.15,2.16
区間を使った計算の総まとめ的な問題。これまでの、区間の積和演算の知識を使うと直感的にも演算によって導き出される区間が変わりそうな気はする。
この欠点のない区間算術演算パッケージは、できなさそうな気がするんだけどできちゃうんだろうなというのが最初の印象。
ちょっと調べると、本に書いてある通りこれは相当難しい問題らしい。例えばここでは幾つかの議論へのリンクが貼られている。

抵抗値の計算の時、誤差ってどのように扱うって習ったのかな。。。?そういえば記憶が曖昧な気がする。計算時にはそもそも誤差はないものとして扱うことしかしてこなかったかも。

ということで、消化不良ながらも区間つきの値の演算についての項目は終了。一見単純そうなのに、実はかなり難しい問題の典型的な例だったみたい。

MIT OCW

Lecture 2B | MIT 6.001
本日の MIT ビデオは 2B の後半。

・抽象化レイヤ
・pair の pair を用いて、任意の大きさのデータブロックを定義できる
・cons/car/cdr を自前で用意
　・データ的なものを関数を用いて表現する

問題解答

問2.11

(define (mul-interval x y)
	(cond ((< 0 (lower-bound x)) (make-interval (* (lower-bound x) (lower-bound y))
                                              (* (upper-bound x) (upper-bound y)))
         ((= (lower-bound x) 0) (make-interval 0
                                               (* (upper-bound x) (upper-bound y))))
         ((< (lower-bound x) 0) (make-interval (* (lower-bound x) (upper-bound y))
                                               (* (upper-bound x) (upper-bound y))))
         ((= (upper-bound x) 0) (make-interval (* (lower-bound x) (upper-bound y))
                                               0))
         ((< (upper-bound x) 0) (make-interval (* (lower-bound x) (upper-bound y))
                                               (* (upper-bound x) (lower-bound y))))
         ((= (lower-bound y) 0) (make-interval (* (lower-bound x) (upper-bound y))
                                               0))
         ((< (lower-bound y) 0) (make-interval (* (lower-bound x) (upper-bound y))
                                               (* (upper-bound x) (lower-bound y))))
         ((= (lower-bound y) 0) (make-interval 0
                                               (* (lower-bound x) (lower-bound y))))
         ((= (lower-bound y) 0) (make-interval (* (upper-bound x) (lower-bound y))
                                               (* (lower-bound x) (upper-bound y)))))))

9 つに場合分けすることはできたけれども、いずれかの値が 0 でない場合は常に二回乗算がおこなわれるような。。。?
→問題は"二回以上"だけど、正しくは"二回より多く"。また、場合分けの仕方がダメだった。
また、x と y の区間が被らない前提で考えてしまった。

本来なら xy それぞれについて

• 完全に負
• ゼロをまたぐ
• 完全に正

の、3×3通りについて考えないといけなかった。

問2.12

(define (make-center-percent v percent)
  (make-interval (* v (- 1.0 (/ percent 100.0)))
                 (* v (+ 1.0 (/ percent 100.0)))))

(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))

(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))

(define (percent i)
    (* (/ (width i) (center i)) 100))

P54 は丸々問題なので時間がかかる。

それにしても、WordPress でタグを打ちながら記事を書くのがいい加減辛い、、、、
テーマも適当だし、いい加減もっと手軽なものに移行したい。

MIT OCW

Lecture 2B | MIT 6.001
本日の MIT ビデオは 2B の前半。 pair を使って有理数を定義したり、演算をしたり。

pair
car
cdr
抽象レイヤ
約分のタイミングを例に、システムのデザインの話

問題解答

問2.9
区間を値 v と w で表して、それを演算するという話。
区間 x1 と x2 があって、その差の区間は

下限 : (v2-w2) – (v1+w1)
上限 : (v2+w2) – (v1-w1)
上限-下限 : ((v2+w2) – (v1-w1)) – ((v2-w2) – (v1+w1))
= v2-v1-v2+v1 +w2+w1+w2+w1
= 2(w1+w2)

同様に和の区間は

下限 : (v2-w2) + (v1-w1)
上限 : (v2+w2) + (v1+w1)
上限-下限 : ((v2+w2) + (v1+w1)) – ((v2-w2) + (v1-w1))
= v2+v1-v2-v1+w2+w1+w2+w1
= 2(w1+w2)

よって、両者とも区間の幅の関数になる。

乗算は
値1 : (v1+w1) * (v2+w2) = (v1v2+v1w2+v2w1+w1w2)
値2 : (v1-w1) * (v2+w2) = (v1v2+v1w2-v2w1-w1w2)
値3 : (v1+w1) * (v2-w2) = (v1v2-v1w2+v2w1-w1w2)
値4 : (v1-w1) * (v2-w2) = (v1v2-v1w2-v2w1+w1w2)

値をどれか取って確かめる。

差 : 値4-値1:
(v1v2-v1w2-v2w1+w1w2) – (v1v2+v1w2+v2w1+w1w2)
= (-v1w2-v2w1) – (v1w2+v2w1)
= -2(v1w2+v2w1)

和 : 値4+値1:
(v1v2-v1w2-v2w1+w1w2) + (v1v2+v1w2+v2w1+w1w2)
= 2(v1v2+w1w2)

いずれも v1,v2 が残ってしまう

問2.10
ゼロ除算の問題?

(define (div-interval x y)
  (if (or (= (upper-bound y) 0) (= (lower-bound y) 0))
      (display "error")
      (mul-interval x
                    (make-interval (/ 1.0 (upper-bound y))
                                   (/ 1.0 (lower-bound y))))))

今日も MIT OCW の視聴から。

MIT OCW

Lecture 2A | MIT 6.001
∑計算
高階関数
Fixed-point
average-damp
Newton法

質疑応答もあわせてλ式と普通の関数との書き換えとか、教科書であまり触れられていない内容が解説されていて復習にちょうどいい。

本文

2.1.4 拡張問題:区間算術演算
区間を持った値の扱いについて。

問題解答

問2.7

(define (lower-bound x)
  (car x))

(define (upper-bound x)
  (cdr x))

(define v (make-interval 1 2))
(upper-bound v)
(lower-bound v)

問2.8

(define (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                         (- (upper-bound x) (lower-bound y))))

ここらへんはさすがに簡単。

ビデオの視聴が一時間かかるから、本をやる時間が結構削られる。ビデオの内容が本でやってる内容に追いつくまではこんなペースになるのかな。

Church 数について何とか片がついたので引き続き本を進めます。その前に昨日から始めた MIT の授業視聴。1A1B あたりはまだまだ基礎の部分なので大丈夫な感じ。それでも、本だけだと取りこぼしてしまう内容を拾えたりして教えてくれる人の存在って重要だよなーとシミジミ思います。

MIT のコースを見てて地味に嬉しいのが、20-30 分くらいで内容が区切られてて一旦小休止が入るところです。このタイミングが結構絶妙で、集中力が切れるなーっていうくらいで休憩になるのでいい感じでリフレッシュして改めて講義に集中できるんですね。これは集中力の続かない私にも嬉しいです。

ビデオは 1B。繰り返し、再帰、計算量、フィボナッチ数列、ハノイの塔。
繰り返し版のフィボナッチ数列は省いていた。

午前中に別作業をしてしまったために SICP 本文はお休み。

今日から復習も兼ねて MIT の SICP コースのムービーもみてみることにしました。
とりあえずは一日一本、学習がおわっているところまでみてみるつもりです。

ムービーをみた感じ、授業では SICP の中の細かいところまでは突っ込んでいない感じです。自分が理解する範囲も SICP で言及されている内容が最大で、そこから外れている部分は目を瞑るっていう感じがいいのかも。問2.6 であれば SICP で提示されている add-1 の導出まで手をつけるのはやりすぎたかなという感じ。

問題解答

問2.6
今日こそは片をつけたい Curch 数。

SUCC の求め方についてはひとまず横に置いておいて、問題に集中する。

・(zero と add-1 を使わずに)one と two を直接定義せよ.

(define zero (lambda (f) (lambda (x) x)))
(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
(define three (lambda (f) (lambda (x) (f (f (f x))))))

・(add-1 の繰り返し作用させず)加算手続き + を直接定義せよ.

結局わからなかったので先人の知恵を拝借しつつ回答。

a+b
((two inc) ((three inc) 0))

three を計算した結果に two 追加して演算する : (f f) (f f f)

a*b
((two (three inc)) 0)

(three inc) という関数を用いて two という演算をする : (f f f) (f f f)

b^a
(((two three) inc) 0)

three という関数を用いて two という演算をする : ((f f f) (f f f))

言語化するともやっとする。ちゃんと理解できていないんだろうなぁ。

(define (sum a b)
  (lambda (f) (lambda (x) (a f) ((b f) x))))

(((sum two three) inc) 0)

(define (pow a b)
  (lambda (f) (lambda (x) (((b a) f) x))))

(((pow two three) inc) 0)

(define (mult a b)
  (lambda (f) (lambda (x) ((a (b f)) x))))

(((mult two three) inc) 0)

とりあえず課題はおわり。ただ、全く消化しきれている気がしない。
λ計算と展開あたりがかなりダメな予感。