fullfun?またはone-to-one?

関数 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章も終わり。