Scheme手習い(9) 集合と関数
第7章「友達と親類」では集合と関数を題材に取ります
プログラミング的にはあまり新しい話はない気がするので何を書いたらいいものやら
作者の狙いは何
ここまでで覚えた書き方で数学の概念がこんな風に表現できますよ、みたいな感じ？
私はそういう話好きだからいいんですけど
淡々といきます
(define set? (lambda (lat) (cond ((null? lat) #t) ((member? (car lat) (cdr lat)) #f) (else (set? (cdr lat))))))
set(集合)とはlatであって要素に重複がないもの、という定義です
latかどうか（要素がアトムかどうか）は数学とは関係ないですけどね
latだけどequal?で判定してるから数だってOKだよ、とも書いてあります
じゃあリストが要素になっても悪くはなそうですが
この本ではそういうことになってるということでまあ
latの要素に重複があったら取り除いてsetにするmakeset
(define makeset (lambda (lat) (cond ((null? lat) (quote ())) ((member? (car lat) (cdr lat)) (makeset (cdr lat))) (else (cons (car lat) (makeset (cdr lat)))))))こんなに短くて驚きましたか。
そうでもないですがmember?が使えなかったらもっと長くなりますね
実行すると少し直感に反する順番の結果になります
> (makeset '(apple peach pear peach plum apple lemon peach))
'(pear plum apple lemon peach)こちらの定義ならすんなりした結果
でもソース的には上のほうが好きかなあ
(define makeset (lambda (lat) (cond ((null? lat) (quote ())) (else (cons (car lat) (makeset (multirember (car lat) (cdr lat))))))))
> (makeset '(apple peach pear peach plum apple lemon peach))
'(apple peach pear plum lemon)set1がset2のsubset(部分集合)である、とは
(define subset? (lambda (set1 set2) (cond ((null? set1) #t) (else (and (member? (car set1) set2) (subset? (cdr set1) set2))))))
set1のすべての要素がset2に含まれているということ
このへん、いちいち(else (condと書いてから簡単化してます
まだ千本ノックが続いてるということでしょうか
subset?ではさらにandを使って(else #f)を消す、ということもやってます
元はこれ
(define subset? (lambda (set1 set2) (cond ((null? set1) #t) ((member? (car set1) set2) (subset? (cdr set1) set2)) (else #f))))
andで書いたほうがいいんでしょうかね
まあ(else #f)っていうのが余分感あるってのは思いますが
気分的なもの以外に差は？
set1とset2が等しい、とはset1がset2のsubsetであり、かつset2がset1のsubsetである、ということ
感覚的には「set1とset2に同じ要素が含まれていること」なんですが
そのままだとプログラムにしにくいですね
数学でもこういう書き方よく出てきます
そう言わないと数学的に言ってもあいまいってことなんでしょうか
(define eqset? (lambda (set1 set2) (cond (else (and (subset? set1 set2) (subset? set2 set1))))))
(cond (elseはどうしても書かずにいられないんでしょうか
そのわりには戒律にもなってないし
condがない関数なんかインラインに展開すればいいんだよとかそういう話なんでしょうか
求む解説
(define eqset? (lambda (set1 set2) (and (subset? set1 set2) (subset? set2 set1))))
これね
set1とset2が交わっている(intersect?)とは、set1とset2に共通の要素があるということ
プログラムで書くと、set1の要素のうちどれかがset2の要素であること、ということになります
set2の要素のうちどれかがset1の要素であること、でも同じ
(define intersect? (lambda (set1 set2) (cond ((null? set1) #f) (else (or (member? (car set1) set2) (intersect? (cdr set1) set2))))))subset?とintersect?を比べてください。
ほほう
andとor、#tと#fが入れ替わってるだけですね
こういう関係はandとorまで持っていったからわかると言えるかもしれません
続いてintersect(積集合)、union(和集合)、xxx(差集合)を定義します
ここまで集合の話
ここからだんだんと関数の話になっていきます
関数と言っても関数型プログラミングというときの関数とも高校で習う数学の関数とも
イメージが異なります
集合を使って関数を定義してやろうという話
ペアは2つのS式だけからなるリスト
ただし
Schemeのペアというのは(a . b)って表わされるやつですね
(cons 'a 'b)で作るやつ
上で言う「ペア」は(cons 'a (cons 'b '())で作るものです
さらに、ペアの左の要素を取るfirst、右の要素を取るsecond、ペアを作るbuildを定義
まだ(cond (else が出てきます
なにが作者にそこまでさせているのか
relation(関係)とはペアの集合
なんでペアの集合が関係なのか
たとえば1、2、3という数の中で大小の関係を定義するとすれば
((1 2) (1 3) (2 3))という集合を定義して
この集合にfirst = a、second = bとなる要素があるときa < bとする
と決めてやれば大小の関係を定義したことになります
って話
なぜか本にはrel?という関数は出てきません
なぜでしょうか
こんな感じかと思うんですが何か落とし穴があったりするんでしょうか
(define rel?
(lambda (rel)
(cond ((null? rel) #t)
((not (a-pair? (car rel))) #f)
((member? (car rel) (cdr rel)) #f)
(else (rel? (cdr rel))))))この本ではnotが定義されてないので若干反則気味
notを使わなくても書けなくはないですがなんとなく
set?を使う手もあるか
notを定義するならこうかな
(define not
(lambda (x)
(cond (x #f)
(else #t))))これはandやorと違って普通に関数で書いても大丈夫
さていよいよ関数
有限関数とは、ペアのリストであって、各ペアの第1要素はほかのどのペアの第1要素とも
同じでないものと表現できます
数学では無限集合だって自由に考えられるので有限に限ることはないんですが
リストで表現するとどうしても有限集合になってしまいますね
遅延リストだったら無限集合も表現できるかな？
でも所詮は加算無限までだろう
たぶん実用（って実用なのかこの本は）的にはあんまり意味なさそう
リスト内包表記だったら？
それはちょっとここでやろうとしていることと合ってない気がする
あと、流れからすれば「関係であって」とか「ペアの集合であって」だと思いますが、
各ペアの第1要素が一意なので結局同じことですね
関数定義ではrelってことになってます
「各ペアの第1要素はほかのどのペアの第1要素とも同じでないもの」はset?で判定
(define fun? (lambda (rel) (set? (firsts rel))))
y = f(x)みたいな関数とはイメージが異なりますが
関数をxを与えればyが決まるもの、とシンプルに考えて
第1要素をx、第2要素をyと考えれば確かに関数と言えます
第1要素が同じペアが複数あるとyがひとつに決まらなくなってしまうので困ります
revrel(不勉強にして対応する日本語が思いつきません 逆関係？でいいのかな？)とは
関係に含まれるペアの第1要素と第2要素を入れ替えたもの
(define revrel (lambda (rel) (cond ((null? rel) (quote ())) (else (cons (build (second (car rel)) (first (car rel))) (revrel (cdr rel)))))))
入れ替え部分を抽象化したrevpairを導入
こういうことは日頃からこころがけていきたいものです
(define revpair
(lambda (pair)
(build (second pair) (first pair))))
(define revrel
(lambda (rel)
(cond ((null? rel) (quote ()))
(else (cons (revpair (car rel))
(revrel (cdr rel)))))))全単射とは、関数であって値に重複がないもの、という定義
(define fullfun?
(lambda (fun)
(set? (seconds fun))))引数の名前をfunにしただけで定義域は関数であると空気を読まなければいけません
いきなり全単射が出てくるとアレですね
- 全射
y（さっきそう呼んでたもの）が取りうる値すべてに対し、対応するxがあることです
ここの定義だとこれは最初から満たされてます - 単射
どのyに対しても、対応するxがせいぜい1個しかないということです
ここの定義で言えばsecondに重複がないことですね
fullfunは素直に考えてfull functionだと思うんですが
それが部分関数(partial function)に対する全関数だとすると話と合わない
どこか理解が間違ってるのかな・・・
（実は全射とか単射がどうもちゃんと覚えられない）
fullfun?の別の名前は何でしょう。
one-to-one? (一対一対応)です。
全単射＝一対一対応です
これはまちがいない
全関数と一対一対応は違うよな・・・
(define one-to-one?
(lambda (fun)
(fun? (revrel fun))))(revrel fun)のことは逆関数と言いますね
オチなし
