このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

［参照用 記事］

有限的に扱える集合

雑記／備忘

JSONオブジェクト・インスタンスがあると、そのプロパティ名の集合は有限集合として確定します。たとえば、{"foo":"hello", "bar":12} のプロパティ名の集合は {"foo", "bar"} です。しかしスキーマレベルでは、オブジェクト型のプロパティ名の集合は無限集合になることがあります。{*:any?} という型のプロパティ名集合はすべての文字列からなる集合です。ここで、型のプロパティ名集合とは、その型のインスタンスに出現する可能性があるプロパティ名をすべて含む集合のことです。

Catyスキーマでは、特定の名前のプロパティ名の出現を禁止することができます。例えば、{"foo":never?, "zot":never?, *:any?} と書くと、"foo"と"zot"という名前のプロパティは出現できません。この例では、すべての文字列の集合から "foo", "zot" を除いた集合がこの型のプロパティ名集合です。

結局、JSONオブジェクト型のプロパティ名集合は次のどちらかになります。

  1. 文字列の有限集合
  2. すべての文字列の集合から有限個の文字列を除いた集合

状況を一般化すると、Uを無限集合、A, B はUの有限部分集合として、次のどちらかの種類の集合を扱うことになります。

  1. 有限集合A
  2. 有限集合BのUに対する補集合 Bc = U＼B

有限集合または有限集合の補集合

無限集合Uを固定して、これを全体集合と考えます。以下「集合」といえば、すべてUの部分集合だとします。A、Bなどは有限集合とします。Uに対する補集合を上付きc（Acなど）で表します。X、Yなどは有限集合または有限集合の補集合だとします。つまり、有限集合Aを使って X = A または X = Ac と書けるということです。

有限集合または有限集合の補集合を、有限的に扱える集合と呼ぶことにします。実際、以下のような操作が有限的に行えることをこれから示します。

  1. x∈U に対して x∈X を判定する。
  2. 集合に対するブール演算を行う。つまり、X∪Y、X∩Y、Xc を求める
  3. X = Y を判定する。
  4. X ⊆ Y を判定する。

所属の判定

Xが有限集合 {a1, a2, ..., an} のときは、x∈X は次のことを意味します。

  • x = a1 または x = a2、...、 または x = an

要素の等しさが判定できる前提で、最悪でもn回の等値性判定で x∈X を判定できます。

Xが有限集合 {a1, a2, ..., an} の補集合のとき、つまり X = Ac ならば、x∈X は次のことを意味します。

  • x ≠ a1 かつ x ≠ a2、...、 かつ x ≠ an

要素が等しくないこと（等しいの否定）が判定できるなら、やはり最悪でもn回の非等値性判定で x∈X を判定できます。

ブール演算

有限集合A、Bに対して、A∪B、A∩B は求めることができることを前提します（実際、できますよね）。今回は、有限集合Aに対して、Acも「有限集合の補集合」なので「求めることができる」とします。データの表現としては、有限集合の表現と共に補集合を表すフラグを立てておけばいいでしょう。

まずは、A∩Bc について考えます。Aは有限集合、Bcは「有限集合の補集合」なので無限集合です。Bcが無限でも、Aの要素xを取り出して x∈B を判定していけばいいので、これはいずれ終ります。A = {a1, a2, ..., an} なら、n回の所属性判定で済みます。よって、A∩Bc または Ac∩B の形の計算はできます。

A∪Bc は、(Ac∩B)c と書けます（ド・モルガンの法則）。Ac∩B は計算できるので、その補集合も計算できます（補集合フラグを立てればよい）。Ac∪Bc のときは、(A∩B)c なので、これも計算できます。

X = Ac のときの Xc は Xc = (Ac)c = A なので問題ありません。

以上で、有限的に扱える集合のブール演算は実際に有限的に遂行できることがわかりました。

等しさと包含の判定

A、Bが有限集合のとき、A = B は判定可能であると前提します。A = Bc のときは、有限集合と無限集合なので、常に等しくありません。Ac = Bc かどうかは、A = B を調べればいいのでOKです。

X⊆Y は、X∪Y = Y （または X∩Y = X）と同値なので、ブール演算と等しさの判定ができればその組み合わせになります。が、直接的に包含を判定してみます。A と B が有限集合のとき A⊆B は判定可能とします。Ac⊆B は常に偽です。有限集合が無限集合を含むことはできませんから。A⊆Bc は A∩B = 空 の判定と同じです。Ac⊆Bc は B⊆A に帰着できます。

効率を上げる工夫とかはあるでしょうが、“有限集合かまたは有限集合の補集合”を扱っている限り、コンピュータで計算しても処理はちゃんと終りますね。