gauche.dictionary - ディクショナリフレームワーク ¶ディクショナリはキーから値への写像ができるオブジェクトを表わす抽象クラ スです。このモジュールではディクショナリに対してよく使うジェネリック関数、 および他のディクショナリクラスの上に構築される汎用的なディクショナリクラスを 提供します。
| • ディクショナリのためのジェネリック関数: | ||
| • 汎用ディクショナリ: |
gauche.dictionaryモジュールは、ディクショナリプロトコルとして
以下のジェネリックファンクションを提供します
(call-with-iteratorとsize-ofはgauche.collection
のものです)。
これらのジェネリックファンクションのうち、*がついているものは 各ディクショナリの実装が特定化したメソッドを提供しなければなりません。 +がついているものは、ディクショナリの実装が特定化したメソッドを定義しなければ 適切なデフォルト値が返されます。 それ以外のジェネリックファンクションは、*がついているメソッドを使って 実装されていますが、ディクショナリ実装は効率化のために 特定化されたメソッドを定義しているかもしれません。
dict-immutable?(+),
dict-transparent?(+)
dict-get(*), dict-exists?, size-of(*),
dict-comparator(*)
dict-put!(*), dict-delete!(*),
dict-push!, dict-pop!, dict-update!,
dict-clear!
(If the dictionary is immutable, these methods are not specialized
and the default methods throw an error.)
call-with-iterator(*),
dict-find, dict-any,
dict-fold, dict-fold-right, dict-for-each,
dict-map, dict-keys, dict-values,
dict->alist
これらのジェネリック関数は、ディクショナリ(離散的で有限なキーの集合から値の集合への 写像を表現するデータ構造)に対して共通するアルゴリズムを書くのに便利です。 (理論的には連続した、また無限なキーの集合を考えることもできますが、 実装上は有限集合に限る方がずっと簡潔になります。)
組み込みクラスでは、<hash-table>と<tree-map>が
ディクショナリのインタフェースを実装しています。dbmモジュール群の
提供する<dbm>クラスもそうです。
<dictionary>) ¶{gauche.dictionary}
dictが変更不可なら#tを、変更可能なら#fを返します。
変更不可なディクショナリに対して変更を加えるメソッドを呼ぶとエラーが投げられます。
ディクショナリの実装がこのメソッドを特殊化しなければ、
デフォルトメソッドは#tを返します。
<dictionary>) ¶{gauche.dictionary}
このメソッドが真の値を返した場合、プリティプリンタがディクショナリを表示する時に
その内容も一緒に表示されます。例えば組み込みのハッシュテーブルはtransparentです。
gosh$ (alist->hash-table (map-with-index cons "abcdefghijkl") eqv-comparator) #<hash-table eqv[12]( (1 . #\b) (8 . #\i) (9 . #\j) (2 . #\c) (3 . #\d) (10 . #\k) (11 . #\l) (4 . #\e) (5 . #\f) (0 . #\a) (6 . #\g) (7 . #\h))>
全てのディクショナリがこうではありません。例えばデータベースに基づいたディクショナリ では、インスタンスを表示する度にクエリを走らせたくはないかもしれません。
ディクショナリの実装がこのメソッドを特殊化しなければ、
デフォルトメソッドは#fを返します。
<dictionary>) key :optional default ¶{gauche.dictionary}
keyに関連付けられた値を返します。もしkeyを持つエントリが
ディクショナリに無い場合、defaultが与えられていればそれを返し、
そうでなければエラーが通知されます。
<dictionary>) key ¶{gauche.dictionary}
ディクショナリがkeyをキーに持つエントリを保持していれば#tを、
そうでなければ#fを返します。
<dictionary>) ¶{gauche.dictionary}
キーを比較するのに使われるcomparatorを返します。
註: このメソッドは#tを返すことがあります。ディクショナリが、
キー同士を直接比較しない場合があるからです
(例: <trie>はキーの各要素ごとに比較するので、キーまるごとの比較器というのは
使いません。data.trie - Trie参照)。呼び出し側は#fが返る可能性を常に念頭に置いてください。
<dictionary>) key value ¶{gauche.dictionary}
keyからvalueへの関連づけをディクショナリに追加します。
<dictionary>) key value ¶{gauche.dictionary}
dict-put!と同じ動作です。
<dictionary>) key ¶{gauche.dictionary}
ディクショナリからkeyをキーに持つエントリを除去します。
keyを持つエントリが無ければ何もしません。
<dictionary>) ¶{gauche.dictionary}
ディクショナリを空にします。通常、全キーをループしてひとつづつ消していくよりも
ずっと高速です。
<dictionary>) key value ¶{gauche.dictionary}
(dict-put! dict key (cons value (dict-get dict key '()))) と同じ動作をするメソッドです。具体的な実装によってはもっと効率が良いかもしれません
(keyを2度検索しなくても良い、など)。
<dictionary>) key :optional fallback ¶{gauche.dictionary}
(dict-get dict key)がペアpであれば、
そのエントリの値が(cdr p)で置き換えられ、(car p)の値が
戻り値となります。keyに該当するエントリが無かったり、ペアで無かった場合は
ディクショナリは変更されず、fallbackがあればそれが戻り値となり、
無ければエラーが報告されます。
<dictionary>) key proc :optional fallback ¶{gauche.dictionary}
次のコードのような動作をしますが、具体的な実装はkeyを一度しかルックアップ
しないなどより効率良くなっている場合があります。
(rlet1 x (proc (dict-get dict key fallback)) (dict-put! dict key x))
<dictionary>) proc seed ¶{gauche.dictionary}
dictの各要素に対してprocを呼びシード値を次に渡します。
procは引数を3つとります。エントリーのキー、エントリーの値、それ
にシード値です。最初のシード値はseedです。procからの返り値
は次のprocの呼び出しでシード値として使われます。最後のproc
の呼び出しの結果がdict-foldの返り値として返されます。
dictが<ordered-dictionary>であれば、procは以下のよ
うな結合で呼ばれます。ここで、キーはK0(最小)からKn(最大)ま
でで、それに対応する値がV0からVnまでであるとします。
(proc Kn Vn (proc Kn-1 Vn-1 ... (proc K0 V0 seed)))
<ordered-dictionary>) proc seed ¶{gauche.dictionary}
dict-foldと同じですが、procを適用する結合の順が以下のよう
に逆になります。
(proc K0 V0 (proc K1 V1 ... (proc Kn Vn seed)))
このジェネリック関数は<ordered-dictionary>上にのみ定義されてい
ます。
<dictionary>) proc ¶{gauche.dictionary}
ディクショナリdictの各エントリーのキーと値に対してprocを呼
びます。順序付きディクショナリに対してはprocがキーの昇順に呼ばれ
ることが保証されています。
<dictionary>) proc ¶{gauche.dictionary}
ディクショナリdictの各エントリーのキーと値に対してprocを呼
び、結果をリストにまとめて返します。順序付きディクショナリに対しては結
果が最初のキーの順にならびます(が、procがキーの昇順に呼ばれるこ
とを保証するものではありません)。
<dictionary>) ¶<dictionary>) ¶{gauche.dictionary}
それぞれdict内にあるすべてのキーのリスト、すべての値のリストを返
します。順序付きディクショナリについてはリストの要素はキーの昇順になら
んでいます。
<dictionary>) ¶{gauche.dictionary}
ディクショナリ中の各キーと値の対のリストを返します。対の順番は未定義です。
{gauche.dictionary}
ディクショナリ的な性質を持つデータ型はそれぞれ独自の操作手続きを持っていて、
しかもその多くはジェネリックなディクショナリAPIに直接対応しています。
そうなると、ディクショナリインタフェースを実装するコードは
ひたすらdefine-methodで以下のような似たようなコードを並べてゆくことになりがちです。
(define-method dict-put! ((dict <my-dict>) key value) (my-dict-put! key value))
define-dict-interfaceはこれらのメソッドを一気に定義する簡単な方法です。
各method引数は対応するdict-methodメソッドに対応し、
procがそのメソッドの操作を提供するデータ型特有の手続きです。
例えば<tree-map>のディクショナリインタフェース定義は以下の通りです。
これを見れば要領はわかるでしょう。全てのディクショナリインタフェースをこのマクロで
定義する必要はありません。
(define-dict-interface <tree-map> :get tree-map-get :put! tree-map-put! :delete! tree-map-delete! :clear! tree-map-clear! :comparator tree-map-comparator :exists? tree-map-exists? :fold tree-map-fold :fold-right tree-map-fold-right :for-each tree-map-for-each :map tree-map-map :keys tree-map-keys :values tree-map-values :pop! tree-map-pop! :push! tree-map-push! :update! tree-map-update! :->alist tree-map->alist :transparent? (^_ #t))
{gauche.dictionary}
2つの値のセットを持ち、一方の値をもう一方の値にマップする
双方向マップ(bimap)を提供します。
内部的には、bimapは二つのディクショナリ、leftマップとrightマップを 持っています。bimapがxとyの関係を保持しているとすれば、 leftマップはxをキーとして対応するyを返し、 rightマップはyをキーとして対応するxを返します。
<bimap>は今のところ、厳密な1対1対応のみを扱います。
マップを変更する手続き(bimap-*-put!, bimap-*-delete!等)
は両方のマップを変更し、1対1対応が保たれるようにします。
(将来的に、1対nやn対mの対応もサポートするかもしれません)。
bimapは単なるディクショナリとして、
dict-get等のディクショナリインタフェースを使って操作することもできます。
その場合はleftマップが見えます。すなわちdict-mapに渡されるキーは
leftマップへのキーとなります。
{gauche.dictionary}
二つのディクショナリ、left-mapとright-mapから新たなbimapを作って
返します。用途に応じた適切なディクショナリを選ぶのは呼出側の責任です。
例えば文字列と数値の関係を保持したいなら、一つの方法は以下のとおりです。
(make-bimap (make-hash-table 'string=?) ; string -> number
(make-hash-table 'eqv?)) ; number -> string
キーワード引数on-conflictは、追加されたエントリが既存のエントリと 衝突する場合の振る舞いを指定します。以下の値が有効です。
:supersedeデフォルトの振る舞いです。重複するエントリは、1対1対応を維持するために取り除かれます。
例えば文字列と数値のbimapが、("foo", 1)および("bar", 2)という
組み合わせを保持していたとします。ここで("bar", 2)を追加しようとすると、
最初の2つのエントリは黙って削除され、("bar", 2)だけがbimapに残ります。
このオプションを与えた場合、変更手続きは常に#tを返します。
:error重複エントリが発生する場合はエラーが投げられます。
#f重複エントリが発生し得る場合は、何も変更を行わず、変更手続きは#fを返します。
註: 今のところ、既に存在する関係とまったく同じ関係を追加しようとした場合は 衝突とみなされます。これは将来変更されるかもしれません。
{gauche.dictionary}
bimapのleftマップとrightマップをそれぞれ返します。
返されたディクショナリを呼出側で変更してはなりません。
{gauche.dictionary}
それじれ、bimapのleftマップまたはrightマップからkeyをルックアップして
対応する値を返します。keyを持つエントリが無い場合、
defaultが与えられていればその値を返し、そうでなければエラーを投げます。
{gauche.dictionary}
それぞれ、keyがbimapのleftマップまたはrightマップに存在すれば
#tを、そうでなければ#fを返します。
{gauche.dictionary}
関係(x, y)をbimapに格納します。
この呼び出しの後では、(bimap-left-get x)がyを、
(bimap-right-get y)がxを返すようになります。
bimapの中に既に関係 (x, _) もしくは関係 (_, y) が
含まれていた場合、その衝突の解決はon-conflict引数によって指定できます。
可能な値はmake-bimapの項を参照してください。on-conflict引数が
与えられなければbimap作成時のon-conflictの値が使われます。
{gauche.dictionary}
それぞれ、leftマップもしくはrightマップでkeyを持つエントリをbimapから
削除します。エントリが削除されたら、もう逆方向のマップでも対応するエントリが削除され、
一貫性が保たれます。与えられたキーに対応するエントリが無ければ何もしません。
{gauche.dictionary}
スタックマップは、複数のマップ(ディクショナリ)を積み重ねてひとつのマップのように見せます。
上にあるマップがより下のマップを「シャドウ」します。
例えばネストしたスコープを思い浮かべてください。
ディクショナリとしては、次のように振る舞います。
dict-getは与えれたキーを一番上のマップから順に探し、
エントリが見つかれば直ちにその値を返します。
dict-put!は常に最上位のマップにエントリを追加します。
より下のマップに同じキーを持つエントリがあった場合、それはシャドウされることになります。
最上位以外のマップのエントリを変更したい場合は、
下のstacked-map-entry-update!を使ってください。
dict-delete!は、全てのマップから指定のキーを持つエントリを削除します。
これはディクショナリとしての一貫性のためです。最初に見つかったエントリだけを
削除した場合、より下層のマップに同じキーがあれば、消したはずのキーが消えてないという
ことになってしまいます。最初に見つかったエントリだけを消したい場合は
stacked-map-entry-delete!を使ってください。
dict-foldは、全てのディクショナリを最上位から順に辿ります。
ただし、複数のマップに同じキーがあった場合、最初のエントリ以外は無視します。
{gauche.dictionary}
与えられたディクショナリdic dic2 …からなる新たなスタックマップを
作って返します。最初に指定されたディクショナリが一番上のディクショナリとなります。
dict-foldで使われるキーの比較にはkey-comparatorが使われます。
key-comparatorが省略された場合には、dicの比較器が使われます。
dict-comparatorをスタックマップに適用するとこのキー比較器が返されます。
{gauche.dictionary}
スタックマップsmapの上にdicを追加した新たなスタックマップを作って返します。
キー比較器はsmapから引き継がれます。
{gauche.dictionary}
スタックマップsmapの保持するディクショナリスタックの一番上にdicを追加します。
{gauche.dictionary}
スタックマップsmapの一番上のディクショナリを取り除きます。
smapのディクショナリリストが空の場合はエラーが投げられます。
{gauche.dictionary}
smapの持つディクショナリの数を返します。
{gauche.dictionary}
与えられたキーkeyを持つ最初のディクショナリdに対して
(dict-update! d key proc fallback)を呼び出します。
これはsmapにdict-update!を適用するのとは異なります。
keyが一番上のディクショナリにはなく、しかし他のディクショナリにあった場合、
dict-update!はprocを呼び出した後、その結果を
一番上のディクショナリに挿入し、他のエントリはそのままにします。
{gauche.dictionary}
keyを持つ最初のエントリを削除します。もし他のディクショナリにkeyを持つ
エントリがあった場合、以降はそれが見えることになります。
これはsmapにdict-delete!を適用するのとは異なります。
dict-delete!はkeyを持つ全てのエントリを削除します。
従ってdict-delete!の後にdict-exists?でキーを問い合わせると
必ず#fが返ります。