takatoh's blog – Learning programming languages.
この関数 xxx はどんな関数か、という質問。
(use mymodule)
(define xxx
(lambda (s1 s2)
(cond
((null? s1) (quote ()))
((member? (car s1) s2) (xxx (cdr s1) s2))
(else (cons (car s1) (xxx (cdr s1) s2))))))
(print (xxx '(stewed tomatoes and macaroni casserole)
'(macaroni and cheese)))
^o^ > gosh -I. xxx.scm (stewed tomatoes casserole)
答は s1 に含まれていて s2 に含まれていないすべてのアトムからなるセットを返す関数。(car s1) が s2 のメンバーなら cons せずに、メンバーでないなら cons して再帰している。終了条件は (null? s1) で値は () だ。まあ、見ればわかるよね。
関数 union は、2つのセット s1 と s2 の和集合を返す関数。(car s1) が s2 のメンバーなら cons せずに（なぜなら s2 に含まれているから）、メンバーでないなら cons して再帰すればいい。
(use mymodule)
(define union
(lambda (s1 s2)
(cond
((null? s1) s2)
((member? (car s1) s2) (union (cdr s1) s2))
(else (cons (car s1) (union (cdr s1) s2))))))
(print (union '(stewed tomatoes and macaroni casserole)
'(macaroni and cheese)))
^o^ > gosh -I. union.scm (stewed tomatoes casserole macaroni and cheese)
今度は2つの集合の共通部分に関する関数だ。
関数 intersect? は、セット s1 と s2 が共通部分を持てば #t を返す。
(use mymodule)
(define intersect?
(lambda (s1 s2)
(cond
((null? s1) #f)
((member? (car s1) s2) #t)
(else (intersect? (cdr s1) s2)))))
(print (intersect? '(stewed tomatoes and macaroni)
'(macaroni and cheese)))
^o^ > gosh -I. intersect_p.scm #t
これを or を使って書くと短くなる。
(use mymodule)
(define intersect?
(lambda (s1 s2)
(cond
((null? s1) #f)
(else (or (member? (car s1) s2) (intersect? (cdr s1) s2))))))
(print (intersect? '(stewed tomatoes and macaroni)
'(macaroni and cheese)))
ここで誤植発見。cond の1つ目の質問 (null? s1) に対する値が本（「Scheme手習い」）では nil になっているけど、これは #f の間違いだろう。
^o^ > gosh -I. intersect_p2.scm #t
関数 intersect はセット s1 と s2 の共通部分を返す。
(use mymodule)
(define intersect
(lambda (s1 s2)
(cond
((null? s1) (quote ()))
((member? (car s1) s2) (cons (car s1) (intersect (cdr s1) s2)))
(else (intersect (cdr s1) s2)))))
(print (intersect '(stewed tomatoes and macaroni)
'(macaroni and cheese)))
^o^ > gosh -I. intersect.scm (and macaroni)
※追記あり
s1、s2 のセット2つを引数にとり、s1 が s2 のサブセット（部分集合）のとき #t を返す関数。
(use mymodule)
(define subset?
(lambda (s1 s2)
(cond
((null? s1) #t)
((member? (car s1) s2) (subset? (cdr s1) s2))
(else #f))))
(print (subset? '(5 chicken wings)
'(5 hamburgers 2 pieces fried chicken and light duckling wings)))
(print (subset? '(4 pounds of horseradish)
'(four pounds chicken and 5 ounces horseradish)))
^o^ > gosh -I. subset.scm #t #f
2つのセット s1 と s2 が等しければ #t を返す関数。お互いがお互いのサブセットなら、等しいといえる。これをコードにするとこうなる。
(use mymodule)
(define subset?
(lambda (s1 s2)
(cond
((null? s1) #t)
((member? (car s1) s2) (subset? (cdr s1) s2))
(else #f))))
(define eqset?
(lambda (s1 s2)
(cond
((subset? s1 s2) (subset? s2 s1))
(else #f))))
(print (eqset? '(6 large chickens with wings)
'(6 chickens with large wings)))
^o^ > gosh -I. eqset.scm #t
and を使うともっと短くなる。eqset? だけ示すと：
(define eqset?
(lambda (s1 s2)
(cond
(else (and (subset? s1 s2) (subset? s2 s1))))))
こうなると cond はいらなくなるので、もっと短くなる。
(define eqset?
(lambda (s1 s2)
(and (subset? s1 s2) (subset? s2 s1))))
3行になった。
subset? も and を使うと短くなる。
(use mymodule)
(define subset?
(lambda (s1 s2)
(cond
((null? s1) #t)
(else (and (member? (car s1) s2) (subset? (cdr s1) s2))))))
(print (subset? '(5 chicken wings)
'(5 hamburgers 2 pieces fried chicken and light duckling wings)))
(print (subset? '(4 pounds of horseradish)
'(four pounds chicken and 5 ounces horseradish)))
^o^ > gosh -I. subset2.scm #t #f
今日から7章。集合（セット）が出てきた。セットは、同じアトムが2回以上現れないリストのこと。
まずは、引数として与えられたリストが、セットかどうかを判定する関数 set? から。
(define member?
(lambda (a lat)
(cond
((null? lat) #f)
(else (or (eq? (car lat) a) (member? a (cdr lat)))))))
(define set?
(lambda (lat)
(cond
((null? lat) #t)
((member? (car lat) (cdr lat)) #f)
(else (set? (cdr lat))))))
(print (set? '(apple peaches apple plum)))
(print (set? '(apples peaches pears plums)))
(print (set? '(apple 3 pear 4 9 apple 3 4)))
実行：
^o^ > gosh set.scm #f #t #f
うまくいった。と思ったら、ページ（p.133）の下のほうのやり取りで、「これは次のデータに対してもうまく動きますか。 (apple 3 pear 4 9 apple 3 4)」「はい、member? は eq? ではなく equal? を使って書かれていますから。」とある。いつのまに書き直したんだ、と思って本を読み直したら、5章の最後のやり取りで書き直したことになっているらしい（ほかに該当するところが見当たらない）。この本では eq? は数ではないアトムを引数にとることになっている（eq? の掟）。
とはいえ、実際には eq? は引数が数でも正しく動くので、本と実際とでくい違ってしまっているわけだ。ま、いいか。一応、equal? を使った member? を載せておく。
(use mymodule)
(define member?
(lambda (a lat)
(cond
((null? lat) #f)
(else (or (equal? (car lat) a) (member? a (cdr lat)))))))
これも mymodule.scm に追加しておこう。
次はリストからセットを作る makeset。
(use mymodule)
(define makeset
(lambda (lat)
(cond
((null? lat) (quote ()))
((member? (car lat) (cdr lat)) (makeset (cdr lat)))
(else (cons (car lat) (makeset (cdr lat)))))))
(print (makeset '(apple peach pear peach plum apple lemon peach)))
実行：
^o^ > gosh -I. makeset.scm (pear plum apple lemon peach)
OK。では次に multirember を使って makeset を書け、と。この multirember も equal? を使って書くみたいだな。
(use mymodule)
(define multirember
(lambda (a lat)
(cond
((null? lat) (quote ()))
((equal? (car lat) a) (multirember a (cdr lat)))
(else (cons (car lat) (multirember a (cdr lat)))))))
(define makeset
(lambda (lat)
(cond
((null? lat) (quote ()))
(else (cons (car lat) (makeset (multirember (car lat) (cdr lat))))))))
(print (makeset '(apple peach pear peach plum apple lemon peach)))
^o^ > gosh -I. makeset2.scm (apple peach pear plum lemon)
うまく動いた。けど、この実装での結果が本（p.144）と違っている。たぶん間違っているのは本のほう。だって、makeset の2つの定義では違う動作をするはずなのに、本では結果が同じになってるから。
Scheme手習いからはちょっと脱線して、可変長の引数をとる関数の定義方法。
このページが参考になった。
cf. 可変長引数をとる関数の定義法 ― チキン煮込みチーズミックス4辛
cf. 4.3 手続きを作る ― Gauche ユーザリファレンス
次のように定義する。
(define func
(lambda (a b . c)
(print "a= " a " b= " b " c= " c)))
(func 1 2)
(func 1 2 3 4)
2行目のように引数リストの最後の直前に ‘.’ を入れて書く。こうすると、a、b には最初の2個の引数が渡され、c には残りの引数がリストとして渡される。
^o^ > gosh args2.scm a= 1 b= 2 c= () a= 1 b= 2 c= (3 4)
2個以上の引数を取る関数と本質的に同じ。
(define func
(lambda (a . b)
(print "a= " a " b= " b)))
(func 1)
(func 1 2 3 4)
^o^ > gosh args1.scm a= 1 b= () a= 1 b= (2 3 4)
これは上の場合と違う。通常、仮引数は括弧でくくってリストの形にするけど、引数が0個以上の場合には括弧でくくらない。
(define func
(lambda a
(print "a= " a)))
(func)
(func 1)
(func 1 2 3 4)
こうすると、引数はすべて a にリストとして渡される。
^o^ > gosh args0.scm a= () a= (1) a= (1 2 3 4)
6章の最後に、空リストで数を表現するという面白いのが出てくる。
たとえば 0 は ()、1 は (())、2 は (() ()) という具合だ。この数の表現を使っていくつか関数を書いてみよう。
まずは、ゼロかどうかを調べる関数。
gosh> (define sero?
(lambda (n)
(null? n)))
sero?
gosh> (sero? '())
#t
gosh> (sero? '(()))
#f
つぎに、add1 に相当する関数。
gosh> (define edd1
(lambda (n)
(cons (quote ()) n)))
edd1
gosh> (edd1 '())
(())
gosh> (edd1 '(() ()))
(() () ())
sub1 に相当する関数。
gosh> (define zub1
(lambda (n)
(cdr n)))
zub1
gosh> (zub1 '(() ()))
(())
gosh> (zub1 '())
*** ERROR: pair required, but got ()
Stack Trace:
_______________________________________
ゼロ () に zub1 を適用したらエラーになった。0 以上の整数しか扱えないんだな。
6章の続き。算術式の別の表現というのが出てくる。この別の表現というのは次のようなもの。
この新しい算術式の値を求める関数 value を書け、と。
こんなのでどうだ。
(use mymodule)
(define value
(lambda (nexp)
(cond
((atom? nexp) nexp)
((eq? (car nexp) (quote e+))
(o+ (value (car (cdr nexp))) (value (car (cdr (cdr nexp))))))
((eq? (car nexp) (quote e*))
(o* (value (car (cdr nexp))) (value (car (cdr (cdr nexp))))))
(else
(o^ (value (car (cdr nexp))) (value (car (cdr (cdr nexp)))))))))
(print (value '(e+ 3 8)))
(print (value '(e+ (e* 3 6) (e^ 8 2))))
実行：
^o^ > gosh -I. value2.scm 11 82
うまくいったようだ。
さて、書いてみたコードを見ると、car や cdr が多すぎる。ここで、本（「Scheme手習い」）では、第1の算術式を求める 1st-sub-exp、第2の算術式を求める 2nd-sub-exp、演算子にあたる部分を求める operator を書き、これらを使って value を書き直せ、とある。やってみよう。
(use mymodule)
(define 1st-sub-exp
(lambda (aexp)
(car (cdr aexp))))
(define 2nd-sub-exp
(lambda (aexp)
(car (cdr (cdr aexp)))))
(define operator
(lambda (aexp)
(car aexp)))
(define value
(lambda (nexp)
(cond
((atom? nexp) nexp)
((eq? (operator nexp) (quote e+))
(o+ (value (1st-sub-exp nexp)) (value (2nd-sub-exp nexp))))
((eq? (operator nexp) (quote e*))
(o* (value (1st-sub-exp nexp)) (value (2nd-sub-exp nexp))))
(else
(o^ (value (1st-sub-exp nexp)) (value (2nd-sub-exp nexp)))))))
(print (value '(e+ 3 8)))
(print (value '(e+ (e* 3 6) (e^ 8 2))))
実行：
^o^ > gosh -I. value3.scm 11 82
うまくいった。
最後に、今書いたコードを、最初の算術式の表現、つまり演算子に当たるアトムが中置きに成っている算術式の表現に合うように直せるか、ときた。
これは簡単、1st-sub-exp と operator を書き直せばいい。
(define 1st-sub-exp
(lambda (aexp)
(car aexp)))
(define operator
(lambda (aexp)
(car (cdr aexp))))
value は書き直す必要がない。なぜなら、value は 1st-sub-exp、2nd-sub-exp、operator という3つの補助関数を使って抽象化されているからだ。こうやって抽象化しておけば、算術式の表現が変わっても補助関数を直すだけでいい、というわけだな。
第8の戒律
表現から抽象化するに際し、補助関数を使用すべし。
今日から6章だ。算術式と、算術式の表現という言葉が出てきた。算術式とは（数を含む）アトムか、2つの算術式を＋か×か↑で結合したもの。一方、算術式の表現とは算術式を括弧でくくったものだ。
例を示そう。まずは算術式の例：
ここで注意しておかなきゃいけないのは、＋や×、↑ はアトムであって前に書いた演算子（o+とかo*とか書いたやつ）ではないってこと。
それから算術式の表現の例：
ポイントは、括弧でくくったことでS式になったところだ。1 はアトムなので括弧でくくらなくてもS式だ。算術式がS式になったことで Scheme で扱えるようになった。
関数 numbered? は算術式の表現、つまりS式が、＋、×、↑ を除いて数だけを含むかどうかを判定する関数。特殊文字は使えないので、これからは e+、e*、e^ （e は expression の e）と書こう。
p.101 にヒントがあるので、numbered? を書いてみよう。
(use mymodule)
(define numbered?
(lambda (aexp)
(cond
((atom? aexp) (number? aexp))
((eq? (car (cdr aexp)) (quote e+))
(and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
((eq? (car (cdr aexp)) (quote e*))
(and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
(else
(and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp)))))))))
(print (numbered? 1))
(print (numbered? '(1 e+ 3)))
(print (numbered? '(1 e+ (3 e* 4))))
(print (numbered? '((3 e^ 2) e+ 5)))
実行してみよう：
^o^ > gosh -I. numbered.scm #t #t #t #t
うまくいったようだ。
関数 value は算術式の自然な値を返す関数。たとえば (value (1 e+ 2)) は 3 を返す。これもヒントを見ながら書いてみよう。
(use mymodule)
(define value
(lambda (nexp)
(cond
((atom? nexp) nexp)
((eq? (car (cdr nexp)) (quote e+))
(o+ (value (car nexp)) (value (car (cdr (cdr nexp))))))
((eq? (car (cdr nexp)) (quote e*))
(o* (value (car nexp)) (value (car (cdr (cdr nexp))))))
(else
(o^ (value (car nexp)) (value (car (cdr (cdr nexp)))))))))
(print (value 1))
(print (value '(1 e+ 3)))
(print (value '(1 e+ (3 e* 4))))
(print (value '((3 e^ 2) e+ 5)))
実行：
^o^ > gosh -I. value.scm 1 4 13 14
OKだ。
2つの関数、numbered? と value に共通するのは、引数がアトムでなかった場合、算術式の2つの部分式について再帰するところだ。部分式が算術式であるかどうかがわかれば全体が算術式であるかどうかもわかるし、部分式の値がわかれば全体の値もわかる。
第7の戒律
性質を同じくするすべての構成部分について再帰すべし。
- リストのすべての部分リストについて。
- 算術式のすべての部分式について。
5章もこれで最後だ。
つい先日、ラット lat の中からアトム a を取り除く関数 rember を書いた。今度は、この rember をS式のリスト l からS式 s を取り除くように書き直すと次のようになる。
（おっと、その前に equal? と eqlist? を mymodule.scm に加えておこう）
(use mymodule)
(define rember
(lambda (s l)
(cond
((null? l) (quote ()))
((atom? (car l))
(cond
((equal? (car l) s) (cdr l))
(else (cons (car l) (rember s (cdr l))))))
(else
(cond
((equal? (car l) s) (cdr l))
(else (cons (car l) (rember s (cdr l)))))))))
(print (rember '(cup) '((coffee (cup)) tea (cup) and ((hick) cup))))
^o^ > gosh -I. rember2.scm ((coffee (cup)) tea and ((hick) cup))
これを簡単化せよ、と。まあ、難しくはない。equal? は任意のS式を比較できるんだから、(atom? (car l)) の条件は必要ない。というわけでこうなる。
(use mymodule)
(define rember
(lambda (s l)
(cond
((null? l) (quote ()))
(else
(cond
((equal? (car l) s) (cdr l))
(else (cons (car l) (rember s (cdr l)))))))))
(print (rember '(cup) '((coffee (cup)) tea (cup) and ((hick) cup))))
^o^ > gosh -I. rember3.scm ((coffee (cup)) tea and ((hick) cup))
さて、まだ簡単化できる。cond が二重になっているのが冗長だから、ひとつにしてしまえばいい。
(use mymodule)
(define rember
(lambda (s l)
(cond
((null? l) (quote ()))
((equal? (car l) s) (cdr l))
(else (cons (car l) (rember s (cdr l)))))))
(print (rember '(cup) '((coffee (cup)) tea (cup) and ((hick) cup))))
だいぶ簡単になった。うまく動くか試してみよう。
^o^ > gosh -I. rember4.scm ((coffee (cup)) tea and ((hick) cup))
OK！これで5章は終わり。