Scheme手習い　第７章　友達と親類（その３）

更に集合演算を習います。

ノート：

a-pair

要素が二つのリストであると言う述語。

引数xがアトムであれば偽
xが空であれば偽
xのcdrが空であれば偽
xのcdrのcdrが空であれば真
それ以外は偽

アトム、空リスト、要素が一つしか無いリストを評価してもエラーにならない様な定義にしてある。

> (a-pair? '(paer pear))
#t
> (a-pair? '(3 7))
#t
> (a-pair? '((2) (pair)))
#t
> (let ((l '(full (house))))
    (a-pair? l))
#t
>

first、second、build

ペアに対する補助関数。どうしても定型に拘りが有る模様で、ここでも意味の無いcondが登場。冗長部分を省くと

(define first
  (lambda (p)
    (car p)))
(define second
  (lambda (p)
    (car (cdr p))))
(define build
  (lambda (a1 a2)
    (cons a1 (cons a2 '()))))

適当な例で試す。

> (build 'a 'b)
(a b)
> (first (build 'a 'b))
a
> (second (build 'a 'b))
b
>

thirdは何故登場したのか？

rel、fun

relはペアの集合、即ち重複したペアが存在しないペアのリストとの事。何故かrel?は登場しない。

funは関数を表していると言う事で、最初の例の様に第１要素に4を持つペアが複数あってはいけない。本当の数学的な意味ではひとつのxに対して複数のyが存在する事もあるが、ここではひとつのxに対してはひとつのyしか存在しない事を前提とする。またxはリストに存在しているものだけなので部分関数である。

fun?は引数relがfunであると言う述語。

リストの各要素の最初の要素を集めたリストが集合であれば（重複がなければ）真
そうでなければ偽

> (let ((rel '((4 3) (4 2) (7 6) (6 2) (3 4))))
    (fun? rel))
#f
> (let ((rel '((8 3) (4 2) (7 6) (6 2) (3 4))))
    (fun? rel))
#t
> (let ((rel '((b 4) (b 0) (b 9) (e 5) (g 4))))
    (fun? rel))
#f
>

revrel

引数relに適用し、キーと値を逆にしたレルを意味する。

引数relが空であれば空
relが空でなければ、relの最初の要素に対してその第２要素、第１要素からなるペアにrelの残りの部分のキーと値を逆にしたレルを連結したレル

> (let ((rel '((8 a) (pumpkin pie) (got sick))))
    (revrel rel))
((a 8) (pie pumpkin) (sick got))
>

はい。しかし、表現が読みやすさに貢献していることがわかるでしょう。

二番目の定義も正しいが、最初の定義では補助関数を使っていて読みやすいと解釈。

補助関数revpairを使った定義でもう一度評価してみる。

> (let ((rel '((8 a) (pumpkin pie) (got sick))))
    (revrel rel))
((a 8) (pie pumpkin) (sick got))
>

fulfun?

全射とはf:A→Bの時、任意のbに対してf(a)=bとなるaが存在する事。fが単射である場合、異なるbに対応するaはひとつしか存在しない。
ここでは部分写像は前提としていないので、任意のaに対して必ずbが存在しているものとする。
なので、fulfun?は引数funが全単射であると言う述語は、B（第２要素のリスト）に重複がない事が条件となる。

> (let ((fun '((8 3) (4 8) (7 6) (6 2) (3 4))))
    (fullfun? fun))
#t
> (let ((fun '((grape raisin) (plum prune) (stewed prune))))
    (fullfun? fun))
#f
> (let ((fun '((grape raisin) (plum prune) (stewed grape))))
    (fullfun? fun))
#t
>

この定義は引数funが有限関数（あるいは全射）である事が前提なので有限関数ではないfunを評価すると間違った結果となる。

> (let ((fun '((grape raisin) (plum prune) (grape stewed))))
    (fullfun? fun))
#t
>

one-to-one

一対一も全単射と同じなので、キーと値を逆にしても関数になっている（互いに重複がない）事が条件となる。

> (let ((fun '((8 3) (4 8) (7 6) (6 2) (3 4))))
    (one-to-one? fun))
#t
> (let ((fun '((grape raisin) (plum prune) (stewed prune))))
    (one-to-one? fun))
#f
> (let ((fun '((grape raisin) (plum prune) (stewed grape))))
    (one-to-one? fun))
#t
> (let ((fun '((grape raisin) (plum prune) (grape stewed))))
    (one-to-one? fun))
#t
> (one-to-one? '((chocolate chip) (doughy cookie)))
#t
>

fulfun?と同様、関数になっていない入力に対しては間違った答えになる。

プログラミング再入門

プログラミングをもう一度ちゃんと勉強する読書ノート