PEP: 218
Title: Adding a Built-In Set Object Type
Version: $Revision: 1.8 $
Author: Greg Wilson <gvwilson at ddj.com>
Status: Draft
Type: Standards Track
Python-Version: 2.2
Created: 31-Jul-2000
Post-History: 
X-Translator: Matsui "Fe2+" Tetsushi <VED03370 at nifty.ne.jp>

はじめに

    この PEP は Set モジュールを Python 標準ライブラリーに加え、もしそ
    のモジュールが広く使われるならば集合型を Python のビルトイン型にす
    るよう提案する。なぜ集合型が望ましいのか、またその代わりとして辞書
    型を用いる一般的な常套句が相応しくないのかを説明した後、提案者がビ
    ルトインの集合型がどのように動くよう意図しているのか、また予備的な
    Set モジュールがどのように振舞うかを記述する。最後から2番目の節で
    は集合や集合の要素の(不)可変性の問題と Set モジュールが実装する解
    決策について議論する。最後の節では考慮の後捨てられた代替案を見る。


提案理由

    集合は基礎的な数学的構造であり、アルゴリズムを書く時にごく普通に使
    われる。しかし、実装においては非常に稀にしか使われない。それが「正
    しい」構造だったとしても。プログラマーはリストを代わりに使う。リス
    トにある順序の情報が無関係でもなお。そして値による探索が多い。(多
    くの中規模 C プログラムは malloc した配列の中を特定の値がその中に
    あるかどうかを決めるために端から端まで見るようなコードがうんざりす
    るぐらい含まれている…)

    プログラマーはしばしば集合は辞書に「どうでもいい」値を入れることで
    実装できると教えられる。アイテムはこの「集合」に「どうでもいい」値
    を代入することで加えられ、所属テストは dict.has_key で行なわれ、
    del を使って取り除かれる。しかし、集合に対する他の主要な演算 (合併、
    共通部分、差) はこのやりかたで直接サポートされることはない。という
    のも、それらの意味がキー/値ペアを含む辞書型では曖昧だからだ。


長期的提案

    長い目で見たこの PEP のゴールは Python にビルトインの set 型を付け
    加えることである。この型は順不同な一意の値たちの集まりとなる (辞書
    型が順不同なキー/値ペアたちの集まりであるように)。定数集合は通常の
    数学的記法を使って表され、{1, 2, 3} が三つの整数の集合となる。

    曖昧さを避けるため空集合は {-} と書かれ、{} (これはすでに空の辞書
    を表すのに使われている) とはならない。提案者はこの書き方が1要素の
    タプルを表す (3,) と同じ程度に穏当なものだと思っている (より過激な
    戦略は「代替案」の節で議論されている)。また、初期の提案にあった 
    {,} より読み易い。

    繰返しと内包的記法は自明な方法で実装される。すなわち:

        for x in S:

    は S の要素を適当な順番で走る。一方:

        {x**2 for x in S} 

    は S のすべての要素の平方を含む集合を作る。所属は in と not in で
    テストされ、基本的な集合の演算はオーバーロードされた演算子を取り混
    ぜて実装される:

        |               合併
        &               共通部分
        ^               対称差
        -               非対称差

    メソッドとしては:

        S.add(x)        x を集合 S に加える。

        S.update(s)     列 s の全ての要素を集合 S に加える。

        S.remove(x)     x を集合 S から取り除く。もし x が存在しない
	                ならば、このメソッドは LookupError 例外を上
                        げる。

        S.discard(x)    x が集合 S にあれば取り除く。なければ何もし
                        ない。

        S.pop()		任意の要素を取り除いて返すが、要素がなければ 
                        LookupError を上げる。

        S.clear()       この集合から全ての要素を取り除く。

    ビルトインの変換関数が一つある:

        set(x)          列 x の全ての要素からなる集合を作る。


    注:

    1. 我々は合併と共通部分に対してビット演算子 |& を使うよう提案する。
       合併に対して + を使うのは直感的だが、共通部分に * を使うのはそ
       うではない (訊かれたほとんどの人が正しく何をするか答えられなかっ
       た)。

    2. 当初、+ を add の代わりに要素の追加に使うことを考えていた。しか
       し、Guido van Rossum が + は他のビルトインの型に対しては左右対
       称だ (* はそうではないが) と指摘した。add の使用はまたこの演算
       と集合の合併の混同を避ける意味もある。

    3. 集合は LookupException を上げ、KeyError や ValueError は使わな
       い。なぜなら集合の要素はキーでも値でもないからだ。


長期的提案に関する未解決の課題

    PEP 218 の初期の草案ではただ一つの集合型しかなかったが、Python 2.3
    の sets.py 実装では二つの型 Set と ImmutableSet がある。長期的提案
    では一つのビルトイン変換関数 set(繰返し可能型) しかない。ではどう
    やってビルトインの不可変集合型を作るのだろう? 可能性としては、二
    つめの immutable_set() ビルトインを作るか、set() 関数がもうひとつ
    の引数を取れるように、たとえば set(繰返し可能型, immutable=True)
    といった具合にするといったことも考えられるだろうか。

    この PEP では {1,2,3} といった集合記法や {-} で空集合を表すといっ
    た提案をしている。不可変集合と可変集合に対して別の構文がありうるだ
    ろうか? 多分、ビルトインの構文は可変集合用で、不可変集合は可変集
    合から適切な、たとえば immutable_set({1,2,3}) といったビルトイン関
    数を使って作られるという感じだろう。


短期的提案

    集合型に対してそれをビルトインにするに足る十分な需要があるかどうか
    を見定めるため、そしてユーザーに我々の提案する集合の意味論を試す機
    会を提供するため、短期的提案として Set クラスを標準 Python ライブ
    ラリーに付け加えることを提案する。このクラスは上で述べた演算子やメ
    ソッドを提供し、さらに演算に対する名前のついたメソッドも提供する。
    演算子 | に対して union メソッド、|= に対して union_update といっ
    た具合である。

    このクラスでは内部では集合の値を保持するために辞書を使う。値を複製
    するのを避けるために (たとえば集合の値を走る場合など)、クラスは
    Python 2.2 で付け加えられたイテレーターに依存する。

    Tim Peters はこのクラスのコンストラクターは単一の列を引数に取り、
    その列の要素で集合を作るべきだと信じている。彼の議論によれば多くの
    場合、プログラマーは集合を既にある列から作るだろうし、それゆえこの
    使い方が普遍的なものだろうということになる。しかしながら、こうする
    とユーザーに既知の値で集合を初期化する際に余計な一組の括弧を思い出
    すことを要求することになる:

    >>> Set((1, 2, 3, 4))       # case 1

    一方、幾人かの Python 初心者 (他の言語では多くの経験のある人々だが) 
    のフィードバックは人々が「括弧なし」構文をより自然に感じるというこ
    とを示唆している。

    >>> Set(1, 2, 3, 4)         # case 2

    さらにもう一方、もし将来 Python が集合型に対する辞書のような記法を
    採り入れることになった場合、case 2 は冗長である。そういうわけで、
    コンストラクターが一つの繰返し可能な引数だけを取る最初の戦略を採用
    することにした。


可変性

    この提案の中でもっとも解決の難しい疑問は集合は可変な要素を含み得る
    べきかどうかだった。辞書のキーは速く信頼できる探索を可能にするため
    に不可変でなければならない。辞書の要素にも不可変性を要求するのは簡
    単だが、そうすると集合の集合を作れなくなってしまう (こういった集合
    はグラフのアルゴリズムや他の応用でも広く使われている)。

    sets モジュールの中には二つのクラスが実装されている。Set クラスの
    インスタンスは要素を付け加えたり取り除いたりして変更できる。
    ImmutableSet クラスは「凍結」され、要素の変更できない集まりからな
    る。それゆえ、ImmutableSet は辞書のキーや集合の要素になることがで
    きるが更新は許されない。どちらの集合も要素は不可変でハッシュ可能で
    あることが要求される。

代替案

    空集合の記法 {-} の代案として {} を空の辞書とする代わりに空の集ま
    りとして再定義する案が出された。このオブジェクトを空でなくする操作
    により辞書または集合にひっそりと変えられ、その後はその型のオブジェ
    クトとして存続する。このアイディアは既存の Python プログラムへの有
    り得べき衝撃のゆえに拒絶された。dict.keys や dict.values がリスト
    でなく集合を返すように変更する似たような提案も同じ理由で拒絶された。


Copyright

    This document has been placed in the Public Domain.


日本語訳について

    日本語訳は Fe2+ が行ないました。

    誤訳、誤植などありましたらお知らせ下さい。

    元の文書にしたがって、自由な改変および再配布を認めます。