日: 2014年1月20日

関数 fullfunn? （または one-to-one?）は、ファンが全単射、つまり各ペアの第2要素を集めたリストが集合になっているかどうかを判定する。
書いてみよう。

(use mymodule)

(define seconds
  (lambda (rel)
    (cond
      ((null? rel) (quote ()))
      (else (cons (second (car rel)) (seconds (cdr rel)))))))

(define fullfun?
  (lambda (fun)
    (set? (seconds fun))))

(print (fullfun? '((8 3) (4 8) (7 6) (6 2) (3 4))))
(print (fullfun? '((grape raisin) (plum prune) (stewed prune))))
(print (fullfun? '((grape raisin) (plum prune) (stewed grape))))

ここで、seconds という補助関数を作っている。seconds は各ペアの第2要素を集めたリストを作る。それが集合（セット）になっているかどうかを調べているわけだ。

^o^ > gosh -I. fullfun.scm
#t
#f
#t

うまくいったようだ。

ところで、one-to-one? は fullfun? の別名だ。全単射ということは一対一対応だということだからだろう。ここで、one-to-one? の別の定義は思いつけるかという質問が出てきた。ペアの第2要素が集合になっているなら、第1要素と第2要素を入れ替えた (revrel fun) はファンになっているはず。これを使うと次のようになる。

(use mymodule)

(define fun?
  (lambda (rel)
    (set? (firsts rel))))

(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 one-to-one?
  (lambda (fun)
    (fun? (revrel fun))))

(print (one-to-one? '((8 3) (4 8) (7 6) (6 2) (3 4))))
(print (one-to-one? '((grape raisin) (plum prune) (stewed prune))))
(print (one-to-one? '((grape raisin) (plum prune) (stewed grape))))

^o^ > gosh -I. one-to-one.scm
#t
#f
#t

これで7章も終わり。

関数 revrel は、レルの各ペアの第1要素と第2要素を入れ替える関数。rev は reverse の略かな。
書いてみよう。

(use mymodule)

(define revrel
  (lambda (rel)
    (cond
      ((null? rel) (quote ()))
      (else (cons (build (second (car rel)) (first (car rel)))
        (revrel (cdr rel)))))))

(print (revrel '((8 a) (pumpkin pie) (got sick))))

前々回のエントリで作った、first、second、build を使っている。

実行：

^o^ > gosh -I. revrel.scm
((a 8) (pie pumpkin) (sick got))

ここで、ペアの2つの要素を交換する revpair 関数があったとして revrel を書くとどうなるか。こうなる。

(use mymodule)

(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)))))))

(print (revrel '((8 a) (pumpkin pie) (got sick))))

実行：

^o^ > gosh -I. revrel2.scm
((a 8) (pie pumpkin) (sick got))

当たり前だけど、書き直す前と同じ結果になった。

また新しい用語が出てきた。
レル（rel）というのは、ペアの集合（セット）らしい。レルの例：

• ((apples peaches) (pumpkin pie))
• ((4 3) (4 2) (7 6) (6 2) (3 4))

まあ、これはわかる。ファンのほうはよくわからない。「ここではファンは関数（function）を表すために使います。」といいながら、次の質問「(fun? rel) はなんですか。ここで rel は ((8 3) (4 2) (7 6) (6 3) (3 4)) です。」に対して「#tです。というのは (firsts rel) が集合だからです。」と答えている。どういうことさ。
まあいい。ファンは (firsts rel) が集合になるレルだと思っておこう。
で、fun? を set? と firsts を使って書け、と。（その前に set? と firsts を mymodule.scm に追加しておこう）

(use mymodule)

(define fun?
  (lambda (rel)
    (set? (firsts rel))))

(print (fun? '((8 3) (4 2) (7 6) (6 2) (3 4))))
(print (fun? '((b 4) (b 0) (b 9) (e 5) (g 4))))

実行結果：

^o^ > gosh -I. fun.scm
#t
#f

うまくいったようだ。

さて、もうひとつ、有限関数という言葉が出てくる。「有限関数とは、ペアのリストであって、各ペアの第1要素はほかのどのペアの第1要素とも同じでないものと表現できます。」とある。それってファンのことじゃないの？

ペアという構造が出てきた。ペアとは、S式2つからなるリストのことだ。

a-pair?

で、質問はこの引数がペアかどうかを判定する関数 a-pair? を書け、と。どうすればいいかというと、要するに要素が2つのリストかどうかを確認すればいいんだな。言い換えれば、cdr の cdr が null? なら、それはペアだってことだ。

(use mymodule)

(define a-pair?
  (lambda (x)
    (cond
      ((atom? x) #f)
      ((null? x) #f)
      ((null? (cdr x)) #f)
      ((null? (cdr (cdr x))) #t)
      (else #f))))

(print (a-pair? '(pear pear)))
(print (a-pair? '(3 7)))
(print (a-pair? '((2) (pair))))
(print (a-pair? '(full (house))))

実行：

^o^ > gosh -I. apair.scm
#t
#t
#t
#t

できた。

first、second、build

p.120 に first、second、build の定義が載っている。これはペアを作るときと、ペアから部分を取り出すときの関数だ。

(define first
  (lambda (p)
  (cond
    (else (car p)))))

(define second
  (lambda (p)
    (cond
      (else (car (cdr p))))))

(define build
  (lambda (a1 a2)
    (cond
      (else (cons a1 (cons a2 (quote ())))))))

で、これを一行文で再定義しろ、と。ま、簡単、cond の質問が else しかないんだから、cond はなくてもかまわないわけだ。

(define first
  (lambda (p)
    (car p)))

(define second
  (lambda (p)
    (car (cdr p))))

(define build
  (lambda (a1 a2)
    (cons a1 (cons a2 (quote ())))))

たぶん、あとで使うことになるんだろうから、a-pair? とあわせて mymodule.scm に追加しておこう。