For Gauche 0.9.14Search (procedure/syntax/module):

Next: , Previous: , Up: 組み込みライブラリ   [Contents][Index]

6.2 等価性と比較

ふたつのオブジェクトを比較するというのは簡単な話のように思えるかもしれません。 しかし詳しく見てゆくと、一筋縄ではいかない特別なケースが出てきます。 ふたつの手続きが等しいとはどういうことでしょうか。 複素数を何らかの基準で順番に並べるにはどうすばいいでしょう。 一般的な回答は無く、目的によるとしか言えません。 そこで、Schemeでは(Gaucheも)、いくつかの選択肢を用意しておき、 さらに必要ならばユーザが独自の定義を与えることもできるようにしています。


6.2.1 等価

Schemeには等価性を判定する汎用的な述語が3つあります。 また、これらの他に、いくつかの型はその型同士で使える比較手続きを持っています。

Function: eq? obj1 obj2

[R7RS base] 最も高速で、細かい区別ができる述語です。 obj1obj2が同一(identical)のオブジェクト、 すなわち、メモリ上の同じオブジェクトを表している場合に#tを返します。 特に、二つのシンボルもしくは二つのキーワードが同一かどうかを比較するのにeq?が使えます。 ヒープアロケートされるオブジェクトに対しては、ポインタ比較と考えても良いでしょう。

真偽値もeq?で比較できますが、文字と数値はたとえ値が同じオブジェクトであっても 互いにeq?になるかどうかはわかりません。 同一性比較で文字や数値も扱う必要がある場合は、下のeqv?を使いましょう。

(eq? #t #t)               ⇒ #t
(eq? #t #f)               ⇒ #f
(eq? 'a 'a)               ⇒ #t
(eq? 'a 'b)               ⇒ #f
(eq? (list 'a) (list 'a)) ⇒ #f
(let ((x (list 'a)))
  (eq? x x))              ⇒ #t
Function: eqv? obj1 obj2

[R7RS base] obj1obj2がともに正確な数値、もしくはともに (NaN、-0.0以外の)非正確な数値である場合、 (= obj1 obj2)が真であれば#tが、偽であれば#fが 返されます。 -0.0は-0.0とだけeqv?です。

obj1obj2がともに文字である場合、 (char=? obj1 obj2)が真であれば#tが、偽であれば#fが 返されます。 それ以外の場合は、Gaucheではeqv?eq?と同じです。

(eqv? #\a #\a)             ⇒ #t
(eqv? #\a #\b)             ⇒ #f
(eqv? 1.0 1.0)             ⇒ #t
(eqv? 1 1)                 ⇒ #t
(eqv? 1 1.0)               ⇒ #f
(eqv? (list 'a) (list 'a)) ⇒ #f
(let ((x (list 'a)))
  (eqv? x x))              ⇒ #t

NaNの比較には少々奇妙なところがあります。数値比較は、引数に一つでもNaNが 含まれていれば失敗します。したがって(= +nan.0 +nan.0)は常に#fと なります。けれども、(eq? +nan.0 +nan.0)(eqv? +nan.0 +nan.0)#tを返すことがあるかもしれません。

Function: equal? obj1 obj2

[R7RS+] obj1obj2がリストやベクタなどの複合型である場合、 equal?は再帰的に対応する要素同士をequal?で比較してゆきます。 そうでなければ、equal?eqv?と同じようにふるまいます。

もしobj1obj2が互いにeqv?でなく、 組み込み型でもなく、かつ両者のクラスが等しい場合、equal?は ジェネリックファンクションobject-equal?を呼びます。 object-equal?にメソッドを定義することにより、 ユーザ定義のデータ型に対するequal?の振るまいを拡張することができます。

(equal? (list 1 2) (list 1 2)) ⇒ #t
(equal? "abc" "abc")           ⇒ #t
(equal? 100 100)               ⇒ #t
(equal? 100 100.0)             ⇒ #f

;; 0.0と-0.0は数値としては等しい(=)ですが、eqv?は区別し、したがってequal?も区別します。
(equal? 0.0 -0.0)              ⇒ #f

註: この手続きは、obj1obj2がともにペアやベクタを介した 循環構造を持っている場合もR6RSやR7RSに規定されるように値を返します。 ただし、循環構造がユーザ定義データ型を間に挟んでいる場合は 終了しない可能性があります。

Generic Function: object-equal? obj1 obj2

equal?が未知のオブジェクトに対して呼ばれた場合、 このジェネリックファンクションが呼ばれます。自分で定義したクラスに対して このメソッドを定義することにより、equal?で等価判定が行えるように なります。メソッドは、obj1obj2が等価ならば#tを、 そうでなければ#fを返さねばなりません。 オブジェクトの各要素に対して再帰的に等価判定を行いたい場合は、 object-equal?を直接呼ぶのではなく、equal?を各要素に対して 呼ぶようにして下さい。

(define-class <foo> ()
  ((x :init-keyword :x)
   (y :init-keyword :y)))

(define-method object-equal? ((a <foo>) (b <foo>))
  (and (equal? (slot-ref a 'x) (slot-ref b 'x))
       (equal? (slot-ref a 'y) (slot-ref b 'y))))

(equal? (make <foo> :x 1 :y (list 'a 'b))
        (make <foo> :x 1 :y (list 'a 'b)))
  ⇒ #t

(equal? (make <foo> :x 1 :y (make <foo> :x 3 :y 4))
        (make <foo> :x 1 :y (make <foo> :x 3 :y 4)))
  ⇒ #t
Method: object-equal? (obj1 <top>) (obj2 <top>)

このメソッドは、ユーザ定義クラスの2つのインスタンスがequal?であるかを 調べる際に、そのクラスに特殊化したメソッドが無かった場合を捕まえるものです。

このメソッドが呼ばれると、まず登録されたデフォルト比較器の中にobj1obj2を共に処理できるものがあるかどうかを調べ、 あればその比較器の等価述語を使って比較します。デフォルト比較器が引数を処理できなければ #fを返します。デフォルト比較器については 用意されている比較器を参照してください。特に default-comparatorcomparator-register-default!の 項目を見てください。

註: もし、このメソッドと全く同じスペシャライザを 指定してobject-equal?メソッドを定義すると、それはこのメソッドを 置き換えることになり、default-comparatorの動作が壊れることになります。 将来のGaucheのバージョンではそのような再定義は禁止される予定です。 うっかりそういう再定義を行わないように気をつけてください。

しばしば、ふたつの複合型オブジェクトに関して、両者がトポロジー的に等しいこと、 すなわち一方が共有する部分構造を持っている場合にもう一方も同じように部分構造を 共有しているかどうかを調べたいことがあります。equal?はその目的には 使えません。モジュールutil.isomorphの提供するisomorphic?が その目的に使えます。(util.isomorph - 同型判定参照)。


Next: , Previous: , Up: 等価性と比較   [Contents][Index]

6.2.2 比較

等価性はオブジェクトが等しいかどうかしか判断しませんが、しばしば オブジェクトの順序関係を調べたい場合もあります。 ここでも、唯一の「万能順序」があるわけではありません。例えばある複素数が 別の複素数より大きいか小さいかというのは数学的には意味をなしませんが、 数値を含むオブジェクトのリストをソートして一貫性のある結果を得たい場合は 何らかの適当な順序づけを決めておくことは役に立ちます。

Function: compare obj1 obj2

一般的な比較手続きです。obj1obj2より小さければ-1を、 等しければ0を、大きければ1を返します。

obj1obj2が比較できない場合はエラーとなりますが、 compareは多くのSchemeオブジェクト間に全順序を定義しているので、 様々なオブジェクトの比較に使うことができます。この全順序は、 SRFI-114で定義されているものの上位互換です。

組み込みオブジェクトのうち、自然な順序が定義されているものはそれに従って順序づけられます (例えば実数はその数値の大小で、文字はchar<等を使って比較されます)。 また便宜上、通常の意味で大小が定義されないオブジェクトについても ある程度表面的な順序が定義されます。例えば複素数は、まず実部の大小によって 順序づけられ、次に虚部の大小によって順序づけられます。 すなわち、1+i2-i22+iはこの順番に並びます。

#f#tより前に来ます。

リストは辞書順で比較されます。すなわち、まず共通のプリフィクスを除きます。 一方が()でもう一方がそうでなければ、()である方が先にきます。 どちらの尾部も空でなければ、尾部の先頭要素同士を比べます。 (この定義により、空リストは全てのリストの「最小」のものになります)。

(ユニフォームベクタを含む)ベクタは、まず長さで比較され、 長さが同じ場合は要素同士が左から比較されます。 リストや文字列とは異なることに注意。

(compare '(1 2 3) '(1 3))
  ⇒ -1  ; (1 2 3) is smaller
(compare '#(1 2 3) '#(1 3))
  ⇒ 1   ; #(1 3) is smaller
(compare "123" "13")
  ⇒ -1  ; "123" is smaller

二つのオブジェクトがともに<object>のサブクラスであれば、 ジェネリックファンクションobject-compareが呼ばれます。

二つのオブジェクトが異なる型で、少なくとも一方が<object>でない時は、 両者の型により順序が決まります。SRFI-114は組み込み型について 次の順序を定めています。

  1. Empty list.
  2. Pairs.
  3. Booleans.
  4. Characters.
  5. Strings.
  6. Symbols.
  7. Numbers.
  8. Vectors.
  9. Uniform vectors (u8 < s8 < u16 < s16 < u32 < s32 < u64 < s64 < f16 < f32 < f64)
  10. 他のオブジェクトすべて
Generic Function: object-compare obj1 obj2

このジェネリックファンクションを特殊化することで compare手続きをユーザ定義クラスに対して動作するように拡張できます。

このメソッドは以下のいずれかの値を返さねばなりません。 -1 (obj1obj2より前)、 0 (obj1obj2は等しい)、 1 (obj1obj2より後)、 #f (obj1obj2は順序づけできない)。

Method: object-compare (obj1 <top>) (obj2 <top>)

このメソッドは、ユーザ定義クラスの2つのインスタンスをcompareする 際に、そのクラスに特殊化したメソッドが無かった場合を捕まえるものです。

このメソッドが呼ばれると、まず登録されたデフォルト比較器の中にobj1obj2を共に処理できるものがあるかどうかを調べ、 あればその比較器の比較手続きを使って両者の順序を判定します。 デフォルト比較器が引数を処理できなければ #f(「比較できない」)を返します。デフォルト比較器については 用意されている比較器を参照してください。特に default-comparatorcomparator-register-default!の 項目を見てください。

註: もし、このメソッドと全く同じスペシャライザを 指定してobject-compareメソッドを定義すると、それはこのメソッドを 置き換えることになり、default-comparatorの動作が壊れることになります。 将来のGaucheのバージョンではそのような再定義は禁止される予定です。 うっかりそういう再定義を行わないように気をつけてください。

Function: eq-compare obj1 obj2

とある全順序に従ってobj1obj2を比較し、前者が小さければ-1、 等しければ0、前者が大きければ1を返します。obj1obj2は どんなSchemeオブジェクトでも良く、また型が違っていても構いません。 次の二つの性質が保証されます。

  • (eq? x y)#tなら、そしてその時に限り、 (eq-compare x y)は0。
  • 結果は、一回のプロセスの実行中で一貫している (ただし、別のプロセスの実行では異なる結果を返すかもしれない)。

これらの性質以外には、順序についていかなる意味もありません。

この手続きは、任意のSchemeオブジェクトをとにかく順序づけたい (一貫してさえいれば、実際の順序は何でも良い)、という場合に使います。


6.2.3 ハッシュ

ハッシュ関数は等価判定述語と関係が深いので、ここで説明します。

Function: eq-hash obj
Function: eqv-hash obj

この2つはそれぞれeq?および eqv?と一緒に使うのに適した ハッシュ関数です。返り値のハッシュ値は、 システムおよびプロセスに依存する値です。動作しているプロセスの境界を 超えてもちまわることはできません。

注意: eq-hash をつかって、数をハッシュしてはいけません。 2つの数はたとえその値が等しくても eq? であることは保証されて いません。

Function: default-hash obj

[R7RS+] equal?と一緒に使うのに適したハッシュ関数です。 R7RSでは、scheme.comparatorライブラリで定義されています (元はsrfi.128)。

obj が、数値、真理値、文字、シンボル、キーワード、文字列、リスト、 ベクタ、ユニフォームベクタのいずれかならば、そのハッシュ値を求めるのには内部ハッシュ関数を 使います。 obj が、それ以外であれば、 hash は総称関数 object-hash を呼んで、そのハッシュ値を計算します。

返されるハッシュ値はhash-saltの値にも依存します。hash-salt はプロセスが走る度に異なる値をとります。

Function: portable-hash obj salt

時に、「ポータブル」なハッシュ値が必要になることがあります。ここでポータブルとは、 プロセスを何度実行しても、また異なるプラットフォームで実行しても、同じオブジェクト に対して常に同じ値となることです。そのようなハッシュ値は、 プロセスの外に保存したり他のプロセスと共有するオブジェクトと一緒に使えます。

この手続きはobjについてその性質を持つハッシュ値を計算して返します。 つまり、同じオブジェクトと同じソルト値が渡されれば同じハッシュ値となる、ということです。 ここで、「同じオブジェクト」とは、だいたい外部表現が同じになるものと 考えて構いません。equal?であるもの同士は同じです。 また、オブジェクトをwriteで書き出してreadで読み込んだものは 元のオブジェクトと同じになります。

このことから、read/write不変性をもたないオブジェクトはportable-hash では扱えません。objがそのようなオブジェクトを含まないことは 呼び出し側で保証する必要があります。

saltは非負のfixnumで、ハッシュ関数に変化をつけます。一貫した結果を 得るには同じソルト値を使わなければなりません。

objが数値、真理値、文字、シンボル、キーワード、文字列、リスト、 ベクタ、ユニフォームベクタのいずれでもない場合、ハッシュ値を計算するのに 総称関数 object-hashが呼ばれます。

Function: legacy-hash obj

バージョン0.9.4まで、Gaucheではhashと呼ばれるハッシュ関数が equal?ハッシュテーブル用のハッシュ計算と ポータブルなハッシュ値の計算の両方を兼ねていました。 しかしそれには問題がありました。

  1. ハッシュ関数にソルトを与えることができなかったため、 外部からのデータによる衝突攻撃が可能だった
  2. ハッシュ関数自体があまり良くなかった(特に浮動小数点数)
  3. 多倍長整数と浮動小数点数のハッシュ値計算で、 異なるアーキテクチャで異なる値を返してしまうバグがあった。

既にhashで計算されたハッシュ値を利用しているデータがあるため、 以前のhashで提供していたハッシュ関数をlegacy-hashとして 保存することにしました。古いデータにアクセスする場合に使ってください。 (hash関数自体もデフォルトでは legacy-hashと同様に振る舞いますが、ちょっとした仕掛けがあります。 下の説明を参照)。

新たに書くコードでポータブルなハッシュ値が必要なら portable-hashを使ってください。

Generic Function: object-hash obj rec-hash

この総称関数に対するメソッドを定義することにより、ユーザ定義された 型のオブジェクトはハッシュ値を持つことができ、equal?型のハッシュ テーブルで利用できるようになります。

メソッドは正確な非負整数を返さなければなりません。また、 互いにequal?であるオブジェクト同士に対しては同じハッシュ値を 返さなければなりません。 さらに、objがポータブル(「ポータブル」の意味については 上のportable-hashの説明を参照)の場合には、 ハッシュ値は実行中のプラットフォームやプロセスの状態に依存してはなりません。

メソッドが obj の要素のハッシュ値を必要とする場合には、 それらに対して、rec-hashを呼び出してください。そうすれば 適切なハッシュ関数が再帰的に呼び出されます。例えばobject-hashportable-hash経由で呼び出されている場合、 rec-hashを呼べば同じソルト値でポータブルなハッシュ値が計算されます。

objがいくつかの要素を持っている場合、各要素のハッシュ値を まとめるにはcombine-hash-valueを呼びます。

(define-class <myclass> () (x y))

;; user-defined equality function
(define-method object-equal? ((a <myclass>) (b <myclass>))
  (and (equal? (ref a 'x) (ref b 'x))
       (= (abs (ref a 'y)) (abs (ref b 'y)))))

;; user-defined hash function
(define-method object-hash ((a <myclass>) rec-hash)
  (combine-hash-value (rec-hash (ref a 'x))
                      (rec-hash (abs (ref a 'y)))))

註: object-hashのベースメソッドは、どんな引数に対しても 単一の値を返します (具体的な値は、object-hashdefault-hashから呼ばれた場合はhash-saltに依存します。 それ以外の場合は固定値です)。 これは、オブジェクトの等価性が自由に設定できるからで、 等価性を知らずに意味のあるハッシュ値を計算できないあらです。

この振る舞いは最後の安全ネットと考えるべきで、一般には自分で定義したクラスのインスタンスが ハッシュされる可能性があるなら、必ずobject-hashメソッドを定義するように してください。

Method: object-hash (obj <top>) rec-hash
Method: object-hash (obj <top>)

これら二つのメソッドはシステムで定義されており、 後方互換性およびdefault-comparatorの正しい振る舞いを保証しています。 全く同じスペシャライザを持つメソッドを定義することでこれらを置き換えてしまわないように 注意してください。将来のバージョンでは、これらのメソッドを置き換えるのは エラーになる予定です。

Function: combine-hash-value ha hb

二つのハッシュ値hahbを組み合わせたハッシュ値を返します。 次の性質が保証されます:(= ha1 ha2) かつ (= hb1 hb2) ならば (= (combine-hash-value ha1 hb1) (combine-hash-value ha2 hb2))。 これはユーザ定義のobject-hashメソッドを書くのに便利です。

Function: hash obj

この関数は非推奨となりました。

equal?ハッシュとして使える、objのハッシュ値を返します。 デフォルトでは、この関数はlegacy-hashと同じ値を返します。 しかし、この関数がdefault-hashportable-hashから (object-hashを経由して)呼ばれた場合は、呼び出したハッシュ関数へと 再帰します。

この振る舞いは既存のコードを動かすためのものです。0.9.5より前は、 hashが、ポータブルなハッシュ値にもequal?ハッシュテーブルにも 使えるハッシュ値を計算する唯一の関数でした。object-hashメソッドは ハッシュ値を計算したいオブジェクトだけを引数に取り、もしそのオブジェクトが 指す他のオブジェクトのハッシュ値が欲しいなら、hashを再帰呼び出ししていました。

0.9.5から、object-hashはいくつかのハッシュ関数から呼び出されるようになり、 第2引数に再帰すべきハッシュ関数を取るようになりました。 けれども既存のコードを動かなくしてしまうわけにはいきません。そこで、 object-hashのデフォルトメソッド(2引数でマッチするメソッドが 無い場合に呼ばれるもの)が、1引数のobject-hashを呼び出すように 定義されています。既存のobject-hashhashを呼び出していれば、 正しいハッシュ関数へと再帰するというわけです。 新たに書くコードはこの振る舞いに依存してはいけません。 2引数のobject-hashメソッドを定義してください。

Function: boolean-hash bool
Function: char-hash char
Function: char-ci-hash char
Function: string-hash str
Function: string-ci-hash str
Function: symbol-hash sym
Function: number-hash num

[R7RS comparator] これらは、R7RSのscheme.comparatorで定義された、 特定の型のオブジェクト専用のハッシュ関数です。 Gaucheでは、これらの関数は単に引数の型チェックをして(必要なら大文字小文字の 区別をなくした後)、組み込みのdefault-hashを呼び出しているだけです。 これらはscheme.comparatorで定義されているために提供されていますが、 特にポータビリティが必要でなければdefault-hash (あるいは、等価述語によってはeq-hasheqv-hash)を呼んでしまう方が簡単だし高速です。

大文字小文字を区別しない、char-ci-hashおよびstring-ci-hashは、 引数にそれぞれchar-foldcasestring-foldcaseを適用してから hashに渡します。 (char-foldcaseについては文字を、 string-foldcaseについてはフルセットの大文字小文字変換を 参照してください。)

Function: hash-bound
Function: hash-salt

[R7RS comparator] どちらも、正確な非負整数へと展開されます。R7RSでは、 scheme.comparatorライブラリで定義されています。

(註: scheme.comparatorはこれらをマクロと定義しています。処理系が ランタイムオーバヘッドを避けられるようにするためです。 Gaucheでは、呼び出しのオーバヘッドはそれほど問題にならないという 立場から、どちらも手続きにしています。)

ユーザ定義のハッシュ関数は、 結果を0と(hash-bound)の間に限定してもハッシュの質を落とさないことが 保証されます。(ユーザ定義のハッシュ関数は(hash-bound)を気にする 必要はありません。ハッシュテーブルが必要な時にモジュロを取ります)。

ユーザ定義のハッシュ関数はまた、(hash-salt)を計算に組み入れることが できます。展開されるソルト値は、Schemeプロセスの実行ごとに異なる値を 取ったり、ハッシュテーブルごとに異なる値を取るかもしれません。 これは、コリジョン攻撃を回避するためのものです。 組み込みのハッシュ関数は既にソルト値を考慮しているので、 ユーザ定義ハッシュ関数がプリミティブ型のハッシュ値を組み合わせるだけの 場合は、ソルト値を気にする必要はありません。


6.2.4 基本的な比較器

等価性判定と大小比較は色々なデータ構造のパラメータになっています。 treemapはキーの大小を比較します。ハッシュテーブルはキーが等しいかどうかを調べ、 またハッシュ関数と等価性判定に一貫性が無ければなりません。

ジェネリックなデータ構造を作りたければ、こういった比較についてのバリエーションを 抽象化する必要があります。そのために導入されたのが比較器(comparator)です。 これは、比較について関係の深いいくつかの手続きをまとめた構造体です。

比較器を定義したSRFIは二つあります。SRFI-128と呼ばれていた規格は R7RS largeに取り込まれ、scheme.comparatorになりました。 新しいコードではそちらを使うべきです。 Gaucheはscheme.comparatorのAPIを全て組み込みで提供します。 古く、より複雑なのがSRFI-114で、Gaucheはそちらは主に後方互換性のために サポートしています。重要なのは、Gaucheの組み込みの<comparator>オブジェクトは scheme.comparatorの比較器としても SRFI-114の比較器としても使えるということです。


6.2.4.1 比較器クラスとコンストラクタ

Builtin Class: <comparator>

以下の手続きをひとまとめにするレコードです。

型検査述語

オブジェクトがこの比較器によって扱えるかどうかを調べます。

等価述語

二つのオブジェクトが等価かどうかを判定し、等価なら#tを、そうでなければ#f を返します。

順序手続き

二つのオブジェクトの大小関係を判定し、 最初のオブジェクトが二つ目のオブジェクトより小さければ#tを、 そうでなければ#fを返します。

比較手続き

二つのオブジェクトの大小関係を判定し、 最初のオブジェクトの方が小さければ-1を、 二つが等しければ0を、 最初のオブジェクトの方が大きければ1を返します。

ハッシュ関数

オブジェクトのハッシュ値を返します。

scheme.comparatorの比較器は順序手続きを使い、 SRFI-114の比較器は比較手続きを使います。 Gaucheの<comparator>は両方をサポートするために、 自動的に欠けている手続きを補います。 つまり、順序手続きを与えてscheme.comparatorのインタフェースで 比較器を作った場合、Gaucheは自動的に比較手続きを生成しますし、 比較手続きを与えてSRFI-114のインタフェースで比較器を作った場合は 順序手続きが自動生成されます。

比較器は、順序/比較手続き、ハッシュ関数、あるいはその両方を欠いていることもあります。 比較器が順序づけやハッシュに使えるかどうかは、それぞれ comparator-ordered?comparator-hashable?で調べることができます。

Gauche組み込みのデータ型は、コンストラクタで比較器を取ることができます (例:ハッシュテーブル(ハッシュテーブル参照)、 ツリーマップ(ツリーマップ参照))。 また、ソートとマージの手続きも比較器を受け取ることができます (ソートとマージ参照。

Function: make-comparator type-test equal order hash :optional name

[R7RS comparator] 与えられたtype-testequalorderhashの 各関数をまとめて、新たな比較器を作って返します。 R7RSではこの関数はscheme.comparatorで定義されています。

各関数の役割については上の<comparator>の説明を参照してください。

註: scheme.comparatorsrfi.114は両方とも make-comparatorを定義していますが、 scheme.comparatororder手続きを取るところで srfi.114compare手続きを取ります。 scheme.comparatorの方が推奨されるので、 Gaucheでは組み込みのmake-comparatorscheme.comparatorに合わせ、 SRFI-114の方はmake-comparator/compareという名前にしてあります。

各引数は、手続きでなく真偽値を取ることもできます。その場合、既に定義された 手続きが使えるので便利です。但し、引数に真偽値を渡した場合でも、 アクセサは補われた手続きの方を返します。 (例えばtype-test引数に対応するアクセサは comparator-type-test-procedureですが、これは常に手続きを返します。)

type-test引数は、#tもしくは1引数の手続きでなければなりません。 手続きの場合、それは渡されたオブジェクトが比較器の他の手続きに渡せるかどうかを 判定する述語です。#tの場合、どんなオブジェクトに対しても#tを 返す手続きが補われます。

equal引数は二つの引数を取りその等価性を判定する 述語でなければなりません。

order手続きは#fもしくは二つの引数を取り真偽値を返す手続きで なければなりません。手続きの場合、最初の引数が二番目の引数より厳密に手前に ある場合にのみ#tを返します。#fが渡された場合は、 作られる比較器は順序づけには使えません。

hash引数は#fか、一つの引数を取り非負の正確な整数をハッシュ値と して返す手続きでなければなりません。 #fが渡された場合は、この比較器ではハッシュ値を取れないことを意味します。 この場合、呼ばれたらエラーを投げる手続きが補われます。

最後の、省略可能な引数nameはGaucheの拡張です。 どんなオブジェクトでも構いませんが、通常はシンボルが渡されます。 これは比較器を出力する時に使われるだけですが、デバッグには役に立ちます。

Function: make-comparator/compare type-test equal compare hash :optional name

これはSRFI-114比較器のコンストラクタです。SRFI-114ではこれが make-comparatorと呼ばれていますが、名前の衝突を避けるために別の名前を用意しました。 (use srfi.114)した場合は、SRFI-114のコンストラクタが元の名前 で使えるようになります(組み込みのmake-comparatorがシャドウされます。) これは後方互換性のために提供されています。 新たなコードは上に示した組み込みのmake-comparatorを使ってください。

以下の点を除き、上のmake-comparatorとほぼ同じです。

  • 第3引数(compare)には順序手続きのかわりに比較手続きを渡します。 この引数は#fか、二つの引数を取りそれらの大小関係を 判定する手続きでなければなりません。手続きの場合、引数の最初の方が小さいか、 両者が等しいか、最初の方が大きいか、に応じて-1, 0, 1をそれぞれ返さなければ なりません。#fの場合、対象とするオブジェクトの集合に全順序関係がつけられない ことを表します。
  • 比較手続きを与えた場合、equal手続きに#tを渡すことができます。 その場合、等価性の判定は比較手続きが0を返すかどうかで行われます。

6.2.4.2 比較器にまつわる述語とアクセサ

Function: comparator? obj

[R7RS comparator] objが比較器である場合に#tを、そうでなければ#fを返します。 R7RSではこの手続きはscheme.comparatorライブラリで提供されます。

Method: object-equal? (a <comparator>) (b <comparator>)

二つの比較器が等価かどうかをequal?で調べた場合、 比較はこのメソッドを介して、各スロットが等価かどうかで判定されます。 比較器abが別々に作られたものであっても、各スロットの内容が 等価であればequal?とみなされます。

これはGaucheの拡張です。標準は比較器同士の等価性については何も定義していません。 けれども、時には等価判定が便利なことがあります。

(equal? (make-comparator #t equal? #f hash 'foo)
        (make-comparator #t equal? #f hash 'foo))
  ⇒ #t

;; 次の式は、無名手続きがどのようにアロケートされるかによって、#tにも#fにも
;; なり得る。
(equal? (make-comparator (^x x) eq? #f #f)
        (make-comparator (^x x) eq? #f #f))
Function: comparator-flavor cmpr

cmprscheme.comparatorコンストラクタで作られた場合は シンボルorderingを、 SRFI-114コンストラクタで作られた場合はシンボルcomparisonを返します。

アプリケーションは通常両者を区別する必要はありません。一方の比較器は もう一方の比較器としても使うことができるからです。 比較器の実装に特化した最適化をしたい場合にのみ、区別が必要です。

Function: comparator-ordered? cmpr
Function: comparator-hashable? cmpr

[R7RS comparator] 比較器cmprが、オブジェクトの順序づけあるいはハッシュに使える 場合にそれぞれ#tを返します。 R7RSではこの手続きはscheme.comparatorライブラリで提供されます。

Function: comparator-type-test-procedure cmpr
Function: comparator-equality-predicate cmpr
Function: comparator-ordering-predicate cmpr
Function: comparator-hash-function cmpr

[R7RS comparator] 比較器の型検査述語、等価述語、順序手続きおよびハッシュ関数をそれぞれ返します。 R7RSではこの手続きはscheme.comparatorライブラリで提供されます。

これらの手続きは常に手続きを返します。make-comparatororderhash#fを渡した場合でも、エラーを投げるだけの 手続きが返されます。

Function: comparator-comparison-procedure cmpr

[SRFI-114] これはSRFI-114の手続きですが、 scheme.comparator比較器でも時々便利なことがあります。 cmprの型検査述語を満たす二つのオブジェクトを取り、-1、0、1のいずれかを 返す手続きを返します。二つのオブジェクトのうち最初の方が小さければ-1が、 等しければ0が、大きければ1が返されます。 比較器は大小比較可能でなけばなりません(順序手続きが渡されるか、 あるいはSRFI-114コンストラクタで比較手続きが渡されるか)。

Function: comparator-test-type cmpr obj
Function: comparator-check-type cmpr obj

[R7RS comparator] objが比較器cmprで扱えるオブジェクトかどうかを、 cmprの型検査述語を適用して調べます。 comparator-test-typeは結果の真偽値を返します。 comparator-check-typeobjが扱えないオブジェクトである場合に エラーを投げます。

R7RSではこの手続きはscheme.comparatorライブラリで提供されます。

Function: =? cmpr obj obj2 obj3 …
Function: <? cmpr obj obj2 obj3 …
Function: <=? cmpr obj obj2 obj3 …
Function: >? cmpr obj obj2 obj3 …
Function: >=? cmpr obj obj2 obj3 …

[R7RS comparator] 比較器cmprを使ってオブジェクトを比較します。 obj, obj2, obj3 …は全てcmprの 型検査述語を満たさなければなりません。 3つ以上のオブジェクトが渡された場合、比較の順番は規定されていません。

<?<=?>?>=?を使うためには 比較器は順序比較可能でなければなりません。

R7RSではこの手続きはscheme.comparatorライブラリで提供されます。

Function: comparator-hash cmpr obj

[R7RS comparator] 比較器cmprのハッシュ関数を使ってobjのハッシュ値を計算して返します。 比較器はハッシュ計算可能でなければなりません。また、objは 比較器の型検査述語を満たさなければなりません。

R7RSではこの手続きはscheme.comparatorライブラリで提供されます。

Function: comparator-compare cmpr a b

[SRFI-114] ふたつのオブジェクトabの順序を調べ、 aが先 (小さい) なら -1を、 等しければ0を、 aが後 (大きい) なら 1を返します。 abはともにcmprの型検査述語を満たさねばなりません。

単純な比較なら<?等の手続きでできますが、 時に3分岐の比較が便利なこともあります。そのため、SRFI-114から この手続きを採用しました。


6.2.4.3 用意されている比較器

Variable: default-comparator

[SRFI-114] この変数は、様々な場所でオブジェクトを比較する際のデフォルトとして使われる 比較器に束縛されています。

デフォルト比較器は次のとおり定義されており、 ほぼすべてのSchemeオブジェクト間の比較が出来ます。

(define default-comparator
  (make-comparator/compare #t equal? compare default-hash
                           'default-comparator))

定義からわかるように、等価述語、比較手続き、そしてハッシュ計算はそれぞれ equal?comparedefault-hashで処理されます。 組み込みオブジェクト、及び二つの異なる型の間の比較についてはそれらが処理します。

ユーザ定義クラスのオブジェクトについては、 上記手続きがそれぞれジェネリック関数 object-equal?object-compareobject-hashを 呼び出します。これらのメソッドを定義することにより、 default-comparatorの定義域も自動的に拡張されます。

scheme.comparatorは、default-comparatorを拡張する別の方法を定義しています。 下のcomparator-register-default!の項を参照してください。

Function: comparator-register-default! comparator

[R7RS comparator] R7RSではこの手続きはscheme.comparatorライブラリで提供されます。 これは、default-comparator(make-default-comparatorが 返す比較器)の振る舞いをユーザプログラムが拡張できるようにする、 scheme.comparatorが定める方法です。

Gaucheでは、object-equal?object-compareobject-hashに 特殊化したメソッドを定義することでも、デフォルト比較器を拡張できることに 留意してください。詳しくは上のdefault-comparatorの説明を参照のこと。

実際、Gaucheではこれらのジェネリックファンクションを使って、 登録されたデフォルト比較器を処理しています。これらのジェネリックファンクションには、 あらかじめ<top>に特殊化されたメソッドが定義されており、 default-comparatorがユーザ定義クラスのオブジェクトに使われ、 かつそのクラスに特殊化されたメソッドが定義されていない場合を捕まえます。 そして、登録された比較器から与えられた引数に適用可能なものを探し、 見つかればそれを使います。

この手続きがグローバルな副作用を持つことに顔をしかめる人もいるかもしれません。 scheme.comparatorでは、 デフォルトの比較器や登録された比較器が既にカバーしている定義域と 重複する定義域を持つ比較器を登録することを禁じています。 言い換えれば、comparator-register-default!で定義できるのは、 デフォルトの比較器や既に登録された比較器が処理できないオブジェクトを扱う 比較器だけです。従って、新たな比較器を登録することによる副作用は、 それまでdefault-comparatorが扱えなかったオブジェクトを 扱えるようになるというだけで、既に扱えていたオブジェクトに対する default-comparatorの動作が変わってしまうということはありません。

尤も、現実にその条件を強制することは不可能です。 もし、既にデフォルトの比較器の定義域(および、Gaucheのメソッドにより拡張された定義域) と重なるような定義域を持つ比較器を登録してしまったら、その時点でプログラムの 移植性は損なわれます。現在のバージョンでは、comparator-register-default! で登録された比較器は最も低い優先度を持ちますが、その動作をあてにすべきではありません。

Variable: eq-comparator
Variable: eqv-comparator
Variable: equal-comparator

[SRFI-114] それぞれ、等価述語にeq?eqv?equal?を使う 組み込みの比較器です。全てのSchemeオブジェクトを受け付けます。 対応するハッシュ関数(eq-comparatoreq-hasheqv-comparatoreqv-hashequal-comparatorhash)を備えています。 eq-comparatorのみ、eq-compareを使った順序づけが可能です (eq-compareについては比較参照)。

eq-comparatoreqv-comparatorはそれぞれ、 make-eq-comparator and make-eqv-comparatorが返す比較器とは 等価でないことに注意してください。後者の手続きはscheme.comparator で規定されていますが、 ハッシュ関数にはdefault-hashを使うように指定されています。 default-hasheq-hasheqv-hashより重く、 ループのある構造は扱えず、また変更可能なオブジェクトの同一性のみに基づいてハッシュ値を 計算するのには使えません。 こういったdefault-hashの制限を避けたい場合のために eq-comparatoreqv-comparatorを用意しました。

Variable: boolean-comparator
Variable: char-comparator
Variable: char-ci-comparator
Variable: string-comparator
Variable: string-ci-comparator

[SRFI-114] それぞれ、真偽値、文字、文字列を比較する比較器です。 *-ci-*がついている手続きは大文字小文字の区別をしません。 全て、適切なハッシュ関数も備えています。

文字列の大文字小文字の区別をしない比較は、Unicodeのfull-string case conversion に従います (フルセットの大文字小文字変換参照)。

Variable: exact-integer-comparator
Variable: integer-comparator
Variable: rational-comparator
Variable: real-comparator
Variable: complex-comparator
Variable: number-comparator

[SRFI-114] それぞれ、正確な整数、整数、有理数、実数、複素数、そして全ての数値を比較する比較器です。 Gaucheではnumber-comparatorcomplex-comparatorと同じです。

等価性は=により判定されます。 正確な整数、整数、有理数および実数の比較器では、比較手続きは数値の大小に基づいて 判定されます。複素数の比較においては、まず実部の大小が比べられ、実部が等しい場合に 虚部の大小が比べられます。

これらの比較器はNaNを扱いません。 NaNを扱いたい場合は、srfi.114モジュールのmake-inexact-real-comparator 手続きを使って、NaNの比較方法を指定する必要があります。 詳しくはsrfi.114 - 比較器を参照してください。

Variable: pair-comparator
Variable: list-comparator
Variable: vector-comparator
Variable: uvector-comparator
Variable: bytevector-comparator

[SRFI-114] ペア、リスト、ベクタ、ユニフォームベクタ、バイトベクタ(u8vectorの別名)を それぞれ比較するための比較器です。 各データ型の要素についてはデフォルトの比較器(default-comparator)が 使われます。

リストは辞書順で比較されますが(例:(1 2 3)(1 3)より前)、 ベクタの仲間はまず長さが短いものが先に来て、それから内容で比較されることに注意してください (#(1 3)#(1 2 3)より前)。

Variable: time-comparator

<time>オブジェクトを比較する比較器です。時間参照。


6.2.4.4 比較器を組み合わせる

Function: make-default-comparator

[R7RS comparator] デフォルト比較器を返します。Gaucheでは常に唯一のdefault-comparatorが 返されます。 R7RSではこの手続きはscheme.comparatorライブラリで提供されます。

Function: make-eq-comparator
Function: make-eqv-comparator

[R7RS comparator] eq?およびeqv?を等価述語に使う比較器をそれぞれ返します。 これらの関数が返す比較器のハッシュには、default-hashを使うことが scheme.comparatorで規定されていますが、それにはいくつか欠点があります。 変更可能なオブジェクトの同一性に基づいたハッシュ関数が欲しい場合は使えませんし、 循環するオブジェクトでは発散します。大きな構造をハッシュしようとすると遅くなります。 可能ならば、eq-comparatoreqv-comparatorを 使うことを推奨します(用意されている比較器)参照。)

R7RSではこの手続きはscheme.comparatorライブラリで提供されます。

Function: make-reverse-comparator cmpr

[SRFI-114] 与えられた比較器cmprと同じ型検査述語、等価述語、ハッシュ関数を持ち、 大小比較だけが逆になっているような比較器を返します。

Function: make-key-comparator cmpr test key

何らかの構造体があって、その比較に際してはその中の一つの要素を見るだけで良い、 という場合に使える手続きです。

比較器を作って返します。型検査述語にはtestが使われます。 等価述語、比較手続き、ハッシュ関数については、それらの引数にkeyを適用して 得られた値を、比較器cmprの対応する手続きに渡すような手続きとなります。 cmprが比較手続きやハッシュ関数を欠いている場合は、 返される比較器も同様に比較手続きやハッシュ関数を欠いたものとなります。

次の例では、ツリーマップusersは userレコードのusernameスロットだけを見て比較を行います。

(use gauche.record)

(define-record-type user #t #t
  username      ; string
  password-hash ; string
  comment)      ; string

(define users   ; table of users, managed by tree-map
  (make-tree-map
    (make-key-comparator string-comparator user? user-username)))

集合型の比較器を作る手続きについては、srfi.228 - 比較器の合成も参照してください。

Function: make-tuple-comparator cmpr1 cmpr2 …

リスト(x1 x2 …)の各要素をそれぞれcmpr1 cmpr2 … で比較するような比較器を返します。 例えば(make-tuple-comparator c1 c2 c3)が返すのは、 3要素のリストを受け入れ、最初の要素がc1で、二番目の要素がc2で、 最後の要素がc3で比較されるような比較器です。

集合型の比較器を作る手続きについては、srfi.228 - 比較器の合成も参照してください。


Next: , Previous: , Up: 組み込みライブラリ   [Contents][Index]


For Gauche 0.9.14Search (procedure/syntax/module):