9.10.1 ディクショナリのためのジェネリック関数

これらのジェネリック関数は、ディクショナリ(離散的で有限なキーの集合から値の集合への 写像を表現するデータ構造)に対して共通するアルゴリズムを書くのに便利です。 (理論的には連続した、また無限なキーの集合を考えることもできますが、 実装上は有限集合に限る方がずっと簡潔になります。)

組み込みクラスでは、<hash-table>と<tree-map>が ディクショナリのインタフェースを実装しています。dbmモジュール群の 提供する<dbm>クラスもそうです。

自分の定義したクラスにディクショナリのインタフェースを実装するには、 最低限、dict-get、dict-put!、 dict-delete!、dict-fold、dict-comparatorの メソッドを実装してください (データ型がエントリの削除を許さない場合は、dict-delete!の実装を 省略することができます。) 他のジェネリック関数には、これらの基本的なメソッドを使ったデフォルト実装が 提供されます。ただ、他のジェネリック関数についても 自分のクラスに最適化した実装を書くと性能上有利になるでしょう。

註：ディクショナリはコレクションを継承しているので、コレクションを 扱うジェネリック関数はディクショナリに対しても使えます。 例えばエントリの数を得るにはsize-ofジェネリック関数が使えます。

Generic function: dict-get (dict <dictionary>) key :optional default ¶

{gauche.dictionary} keyに関連付けられた値を返します。もしkeyを持つエントリが ディクショナリに無い場合、defaultが与えられていればそれを返し、 そうでなければエラーが通知されます。

Generic function: dict-put! (dict <dictionary>) key value ¶

{gauche.dictionary} keyからvalueへの関連づけをディクショナリに追加します。

Generic function: (setter dict-get) (dict <dictionary>) key value ¶

{gauche.dictionary} dict-put!と同じ動作です。

Generic function: dict-exists? (dict <dictionary>) key ¶

{gauche.dictionary} ディクショナリがkeyをキーに持つエントリを保持していれば#tを、 そうでなければ#fを返します。

Generic function: dict-delete! (dict <dictionary>) key ¶

{gauche.dictionary} ディクショナリからkeyをキーに持つエントリを除去します。 keyを持つエントリが無ければ何もしません。

Generic function: dict-clear! (dict <dictionary>) ¶

{gauche.dictionary} ディクショナリを空にします。通常、全キーをループしてひとつづつ消していくよりも ずっと高速です。

Generic function: dict-comparator (dict <dictionary>) ¶

{gauche.dictionary} キーを比較するのに使われるcomparatorを返します。

Generic function: dict-fold (dict <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)))

Generic function: dict-fold-right (dict <ordered-dictionary>) proc seed ¶

{gauche.dictionary} dict-foldと同じですが、procを適用する結合の順が以下のよう に逆になります。

(proc K0 V0 (proc K1 V1 ... (proc Kn Vn seed)))

このジェネリック関数は<ordered-dictionary>上にのみ定義されてい ます。

Generic function: dict-for-each (dict <dictionary>) proc ¶

{gauche.dictionary} ディクショナリdictの各エントリーのキーと値に対してprocを呼 びます。順序付きディクショナリに対してはprocがキーの昇順に呼ばれ ることが保証されています。

Generic function: dict-map (dict <dictionary>) proc ¶

{gauche.dictionary} ディクショナリdictの各エントリーのキーと値に対してprocを呼 び、結果をリストにまとめて返します。順序付きディクショナリに対しては結 果が最初のキーの順にならびます(が、procがキーの昇順に呼ばれるこ とを保証するものではありません)。

Generic function: dict-keys (dict <dictionary>) ¶

Generic function: dict-values (dict <dictionary>) ¶

{gauche.dictionary} それぞれdict内にあるすべてのキーのリスト、すべての値のリストを返 します。順序付きディクショナリについてはリストの要素はキーの昇順になら んでいます。

Generic function: dict->alist (dict <dictionary>) ¶

{gauche.dictionary} ディクショナリ中の各キーと値の対のリストを返します。対の順番は未定義です。

Generic function: dict-push! (dict <dictionary>) key value ¶

{gauche.dictionary} (dict-put! dict key (cons value (dict-get dict key '()))) と同じ動作をするメソッドです。具体的な実装によってはもっと効率が良いかもしれません (keyを2度検索しなくても良い、など)。

Generic function: dict-pop! (dict <dictionary>) key :optional fallback ¶

{gauche.dictionary} (dict-get dict key)がペアpであれば、 そのエントリの値が(cdr p)で置き換えられ、(car p)の値が 戻り値となります。keyに該当するエントリが無かったり、ペアで無かった場合は ディクショナリは変更されず、fallbackがあればそれが戻り値となり、 無ければエラーが報告されます。

Generic function: dict-update! (dict <dictionary>) key proc :optional fallback ¶

{gauche.dictionary} 次のコードのような動作をしますが、具体的な実装はkeyを一度しかルックアップ しないなどより効率良くなっている場合があります。

(rlet1 x (proc (dict-get dict key fallback))
  (dict-put! dict key x))

Macro: define-dict-interface dict-class method proc method2 proc2 … ¶

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

---

9.10.2 汎用ディクショナリ

Bimap

Class: <bimap> ¶

{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マップへのキーとなります。

Function: make-bimap left-map right-map :key on-conflict ¶

{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を返します。

註: 今のところ、既に存在する関係とまったく同じ関係を追加しようとした場合は 衝突とみなされます。これは将来変更されるかもしれません。

Function: bimap-left bimap ¶

Function: bimap-right bimap ¶

{gauche.dictionary} bimapのleftマップとrightマップをそれぞれ返します。 返されたディクショナリを呼出側で変更してはなりません。

Function: bimap-left-get bimap key :optional default ¶

Function: bimap-right-get bimap key :optional default ¶

{gauche.dictionary} それじれ、bimapのleftマップまたはrightマップからkeyをルックアップして 対応する値を返します。keyを持つエントリが無い場合、 defaultが与えられていればその値を返し、そうでなければエラーを投げます。

Function: bimap-left-exists? bimap key ¶

Function: bimap-right-exists? bimap key ¶

{gauche.dictionary} それぞれ、keyがbimapのleftマップまたはrightマップに存在すれば #tを、そうでなければ#fを返します。

Function: bimap-put! bimap x y :key on-conflict ¶

{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の値が使われます。

Function: bimap-left-delete! bimap key ¶

Function: bimap-right-delete! bimap key ¶

{gauche.dictionary} それぞれ、leftマップもしくはrightマップでkeyを持つエントリをbimapから 削除します。エントリが削除されたら、もう逆方向のマップでも対応するエントリが削除され、 一貫性が保たれます。与えられたキーに対応するエントリが無ければ何もしません。

スタックマップ

Class: <stacked-map> ¶

{gauche.dictionary} スタックマップは、複数のマップ(ディクショナリ)を積み重ねてひとつのマップのように見せます。 上にあるマップがより下のマップを「シャドウ」します。 例えばネストしたスコープを思い浮かべてください。

ディクショナリとしては、次のように振る舞います。

• dict-getは与えれたキーを一番上のマップから順に探し、 エントリが見つかれば直ちにその値を返します。
• dict-put!は常に最上位のマップにエントリを追加します。 より下のマップに同じキーを持つエントリがあった場合、それはシャドウされることになります。 最上位以外のマップのエントリを変更したい場合は、 下のstacked-map-entry-update!を使ってください。
• dict-delete!は、全てのマップから指定のキーを持つエントリを削除します。 これはディクショナリとしての一貫性のためです。最初に見つかったエントリだけを 削除した場合、より下層のマップに同じキーがあれば、消したはずのキーが消えてないという ことになってしまいます。最初に見つかったエントリだけを消したい場合は stacked-map-entry-delete!を使ってください。
• dict-foldは、全てのディクショナリを最上位から順に辿ります。 ただし、複数のマップに同じキーがあった場合、最初のエントリ以外は無視します。

Function: make-stacked-map dic dic2 … ¶

Function: make-stacked-map key-comparator dic dic2 … ¶

Creates a new stacked map with the given dictionaries dic dic2 …, where dic is the topmost dictionary. You can give a comparator key-comparator to be used to compare keys during traversal with dict-fold. If key-comparator is omitted, the comparator from dic is used. The key comparator is returned from dict-comparator on the stacked map.

Method: stacked-map-stack (smap <stacked-map>) (dic <dictionary>) ¶

Creates a new stacked map, adding dic on top of the existing stacked map smap. The key comparator is inherited from smap.

Method: stacked-map-push! (smap <stacked-map>) (dic <dictionary>) ¶

Adds dic on top of the dictionaries smap holds.

Method: stacked-map-pop! (smap <stacked-map>) ¶

Remove the topmost dictionary smap holds. An error is signaled if you attempt to pop from an smap that has no dictionaries.

Method: stacked-map-depth (smap <stacked-map>) ¶

Returns a number of dictionaries smap has.

Method: stacked-map-entry-update! (smap <stacked-map>) key proc :optional fallback ¶

Run (dict-update! d key proc fallback) on the first dictionary d that has the given key.

This differs from running dict-update! on smap; if the topmost dictionary doesn’t have an entry with key but some lower dictionary has, dict-update! takes the existing value and applies proc to it, then insert the result to the topmost dictionary, while the original entry remains intact.

Method: stacked-map-entry-delete! (smap <stacked-map>) key ¶

Deletes the first entry with key. If there’s another entry with key in a lower dictionary, it will become visible.

This differs from running dict-delete! on smap; it deletes all entries with key, so that dict-exists? after dict-delete! is guaranteed to return #f.