(scheme comparator)を理解したい(ただのメモ)

R7RS largeの(scheme comparator)、あるいは(srfi 128)を理解したいという内容
基本的な手続きの使い方やdefault comparatorが理解できたり、hash-tableやsetの利用で活用できるようになることを目的としている

すべての手続きやsyntaxに触れているわけではないので、適宜仕様を見て欲しい
(scheme comparator)/SRFI 128の登場によってwithdrawnになった (srfi 114)についても触れない

comparatorの使いどころ

• ある型について比較関係(等しさや大小)、ハッシュを定義したいときに使う
• comparatorは(scheme hash-table)や(scheme set)で必要

comparatorの使い方

• 型は、述語で区別されている
• 型チェック関数(述語)と比較関係用の手続きとハッシュ生成手続きをmake-comparatorに渡せば作れる

例として、<interval>という自作のrecordについてのmake-comparatorを定義する。

• <interval>はstartとendの2つのメンバーを持つ
• 同じstartと同じendを持つ<interval>は等しい
• startが大きい方の<interval>が大きい
• startが等しければ、endが大きい方の<interval>が大きい
• hashはstartとendの積 (雑だけど)

(define-record-type <interval>
  (interval start end)
  interval?
  (start interval-start)
  (end interval-end))

(define interval-comparator
  (make-comparator interval?
                   (lambda (a b)
                     (and (= (interval-start a)
                             (interval-start b))
                          (= (interval-end a)
                             (interval-end b))))
                   (lambda (a b)
                     (if (= (interval-start a) (interval-start b))
                       (< (interval-end a) (interval-end b))
                       (< (interval-start a) (interval-start b))))
                   (lambda (ival)
                     (* (interval-start ival) (interval-end ival)))))

comparatorと=?を使った等価チェック

• 第一引数がcomparatorで、残りの引数が1つ以上のオブジェクトな手続き
• comparatorに与えた等価チェック手続きについて全ての与えたオブジェクトが等しければ、#tを返し、それ以外の場合は#fを返す

(=? interval-comparator (interval 100 200) (interval 100 200));#t
(=? interval-comparator (interval 100 200) (interval 300 400));#f
(=? interval-comparator (interval 100 200) (interval 300 400) (interval 100 200));#f

comparatorを使った比較( <? , >? , <=? , >=?)

• =?と同様に、第一引数がcomparatorで、残りの引数が1つ以上のオブジェクトな手続き
• すべてのi番目のオブジェクトとj番目のオブジェクト(j>i)について、比較手続き(<? >? <=? >=?)に応じた比較をして、なりたっていれば#tでそうでなければ#fを返す

(<? interval-comparator (interval 100 200) (interval 300 400));#t
(<? interval-comparator (interval 300 400) (interval 100 200));#f
(<? interval-comparator (interval 100 200) (interval 300 400) (interval 500 600));#t
(<? interval-comparator (interval 100 200) (interval 300 400) (interval 10 20));#f

hash値を得る

• comparator-hash手続きにcomparatorとオブジェクトを渡す
• comparatorを作るときに渡したhash生成手続きにオブジェクトを適用する

(comparator-hash interval-comparator (interval 3 4));12
(comparator-hash interval-comparator (interval 5 6));30

pair comparator

• pair同士を比較したり、pairのhashを計算したいときに使う
• car用のcomparatorとcdr用のcomparatorから作られる
• (make-pair-comparator car-comparator cdr-comparator)
• 後述するdefault comparator用に定義されているだけで、ユーザ用ではないかもしれない

pair comparatorの型チェック

• car用comparatorとcdr用comparatorの両方の型チェックを両方とも満たせば#t(それ以外なら#f)

pair comparatorの等価チェック

• car comparatorとcdr comparatorの等価チェックを両方とも満たせば#t(それ以外なら#f)

pair comparatorでの大小比較

• それぞれのcarの値をcar comparatorで比較して大きい方のペアが大きい
• それぞれのcarの値がcar comparatorで等しければ、cdrの値がcdr comparatorで大きい方のペアが大きい

pair comparatorのハッシュ値

• car comparatorのハッシュ値とcdr comparatorのハッシュ値から、実装依存の方法で計算される

{list,vector}-comparator

• list状の構造や、vector状の構造を比較したり、ハッシュ値を計算するのに使う。
• 対象は、scheme標準のlistやvectorでなくてもよい(例えば、ilistとかbytevectorでも良い)
  • listなら、空判定とcar/cdr(head/tail)アクセス方法を与える
  • vectorなら、長さの取得とインデックスアクセス方法を与える
• あとは、各要素用のcomparatorを渡すelement-comparatorと、対象のlist/vector状の構造かの述語を与えるだけ
  例えばilistだと、my-element-comparatorは事前に定義されているとするとこう書ける。

(make-list-comparator my-element-comparator ilist? null? icar icdr)

{list,vector}-comparatorでの比較

• listはcarから比較していき、最初にcarが小さくなるか空リストになったほうが小さい
• vectorはまず長さが短いほうが小さく、長さが同じなら、各要素を頭からどちらかが等しくなくなるまで、element-comparatorで比較し、その大小の結果がvector-comparatorでの比較結果になる

{list,vector}-comparatorでのハッシュ値

• どちらも各要素をelement-comparatorで計算して、それをもとに実装依存の方法でハッシュ値を計算する

make-eq{,v,ual}-comparator

• すべての型に使える
• 等価性はeq?,eqv?,equal?による
• 大小比較は実装依存
• hashは後述する default-comparator のハッシュ計算(実装依存)が使われ、eq?,eqv?equal?とは関係ない

default comparator

• 実装依存な定義のcomparator
• comparatorが必要な場面(例えば、hashテーブルとかset)で、特に独自の比較器が必要ない場合はこれを使う
• (make-default-comparator)手続きで、default comparatorが得られる
• Schemeの既存の型についてはすでに入っている

default comparatorに自作の型を追加する

ユーザ定義した型についても、default comparatorに登録することができる

• comparator-register-default!にユーザ定義型用のcomparatorを渡せば、default comparatorに登録される
• comparator-register-default!に既存のScheme型用のcomparatorを渡して再定義することはできない

default comparatorでの比較の定義

• 型が違うものを比較した場合、等しくないことは保証されていて、以下の規則以外は、実装依存な比較が行われる

ただし、Schemeの既存の型については、次の項目は満たしている

• 空リスト < ペア
• #f < #t
• 数値,char,stringはそれぞれ、= <,char= char<? ,string=? string<?で比較される
• 何かしらの形で、symbolが比較できること(実装依存) (例:symbol->stringにして、文字列比較)
• pairとvectorは各要素にdefault comparatorを使って比較