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

Next: , Previous: , Up: ライブラリモジュール - Gauche拡張モジュール   [Contents][Index]

9.10 gauche.dictionary - ディクショナリフレームワーク

Module: gauche.dictionary

ディクショナリはキーから値への写像ができるオブジェクトを表わす抽象クラ スです。このモジュールではディクショナリに対してよく使うジェネリック関数、 および他のディクショナリクラスの上に構築される汎用的なディクショナリクラスを 提供します。


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

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

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

自分の定義したクラスにディクショナリのインタフェースを実装するには、 最低限、dict-getdict-put!dict-delete!dict-folddict-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} Many dictionary-like datatypes already has their own procedures that directly corresponds to the generic dictionary API, and adding dictionary interface tends to become a simple repetition of define-methods, like this:

(define-method dict-put! ((dict <my-dict>) key value)
  (my-dict-put! key value))

The define-dict-interface macro is a convenient way to define those methods in a batch. Each method argument is a keyword that corresponds to dict-method, and proc is the name of the datatype-specific procedure. Here’s the definition of dict interface for <tree-map> and you’ll get the idea. You don’t need to provide every dictionary interface.

(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} Provides a bidirectional map (bimap), a relation between two set of values, of which you can lookup both ways.

Internally, a bimap consists of two dictionaries, left map and right map. Think a bimap as a relation between xs and ys. The left map takes an x as a key and returns corresponding y as its value. The right map takes an y as a key and returns corresponding x as its value.

Currently, <bimap> only supports strict one-to-one mapping. Mutating interface (bimap-*-put!, bimap-*-delete! etc) modifies both left and right maps to maintain this one-to-one mapping. (In future, we may provide an option to make many-to-one and many-to-many mappings).

A bimap can be used as a dictionary, with the generic dictionary functions such as dict-get. In such cases, the left map takes precedence; that is, the key given to dict-get etc. is regarded as the key to the left map.

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

{gauche.dictionary} Creates a new bimap consists of two dictionaries, left-map and right-map. It is the caller’s responsibility to choose appropriate type of dictionaries; for example, if you want to create a relation between a string and a number, you man want to create it like this:

(make-bimap (make-hash-table 'string=?)  ; string -> number
            (make-hash-table 'eqv?))     ; number -> string

The keyword argument on-conflict specifies what will happen when the added entry would conflict the existing entries. The following values are allowed:

:supersede

This is the default behavior. Duplicate relations are silently removed in order to maintain one-to-one mapping. For example, suppose a bimap between strings and numbers has had ("foo", 1) and ("bar", 2). When you try to put ("bar", 2) with this option, the first two entries are removed. Returns #t.

:error

Raises an error when duplicate relations are found.

#f

When duplicate relations are found, does nothing and returns #f.

Note: At this moment, an attempt to add a relation exactly same as the existing one is regarded as a conflict. This limitation may be lifted in future.

Function: bimap-left bimap
Function: bimap-right bimap

{gauche.dictionary} Returns the left or right map of bimap, respectively. Do not mutate the returned map, or you’ll break the consistency of the bimap.

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

{gauche.dictionary} Lookup the value corresponding to the key in the left or right map of bimap. If no entry is found for key, default is returned if provided, otherwise an error is raised.

Function: bimap-left-exists? bimap key
Function: bimap-right-exists? bimap key

{gauche.dictionary} Returns #f if the left or right map of bimap has an entry of the key, #t otherwise.

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

{gauche.dictionary} Put a relation (x, y) into the bimap. After this, (bimap-left-get x) will return y, and (bimap-right-get y) will return x.

If the bimap already have relations with x and/or y, the conflict is handled according to the value of on-conflict; see make-bimap for the possible values and their meanings. The on-conflict keyword argument can override the bimap’s default setting specified at its creation time.

Function: bimap-left-delete! bimap key
Function: bimap-right-delete! bimap key

{gauche.dictionary} Deletes an relation with the given left key or right key from bimap. Both left and right maps are modified so that the consistency is maintained. If there’s no relations with given key, these are noop.

Stacked map

Class: <stacked-map>

{gauche.dictionary} Stacked map allows you to stack (layer) multiple maps (dictionaries) and treat as if they are a single map. The upper map "shadows" the lower maps. Think of nested scopes, for example.

As a dictionary, it behaves as follows:

  • The dict-get operation searches the given key from the top dictionary to the bottom dictionary, returns the first found entry.
  • The dict-put! operation always put the entry to the topmost dictionary. If there’s an entry with the same key exists in a lower dictionary, it will be shadowed. If you want to alter the existing entry of non-top dictionary, use stacked-map-entry-update!.
  • The dict-delete! operations deletes all the entries with the given key from all the dictionaries. This is for consistency as a dictionary—you don’t want an entry pop up after deleting it. If you want to delete only from the first entry in the stack, use stacked-map-entry-delete!.
  • The dict-fold operation traverse all the dictionaries from top to bottom. When there are duplicate keys, the second and after will be skipped.
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.


Next: , Previous: , Up: ライブラリモジュール - Gauche拡張モジュール   [Contents][Index]


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