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

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

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

参照用 記事

データ構造の基本としてのコレクション

(昨日の続きに近いかも、なんか日刊連載している気分になってきた)

昨日、内容モデルの「モデル」を、構文モデル(正規表現)に限定せず、データ構造モデル、意味モデルも含めて考えたい、と述べました。

データ構造の基本的なことは、SmalltalkJavaなどでおなじみのコレクションAPIで学べますね。

コレクションにもいろいろな流儀や記法があるけれど、ここでは、構文モデルの基本である正規表現(したがってKleene代数*1)につながる形で復習してみましょうかね。

話を簡単にするため、基本データは整数だけにします。整数を項目とするリスト(可変長の列)、バッグ(マルチセット)、セットのリテラル表現を次のように約束します。

  • リスト:(1, 2, 1, 3)
  • バッグ:[1, 2, 1, 3]
  • セット:{1, 2, 3}

これらのコレクションは、“項目の重複出現”と“項目の(線形)順序”の有無により、次のように分類できます。

コレクション種別 重複出現 順序
リスト あり あり
バッグ あり なし
順序付きセット なし あり
セット なし なし

つまり、

  • (2)≠(2, 2), (1, 2)≠(2, 1)
  • [2]≠[2, 2], [1, 2]=[2, 1]
  • {2}={2, 2}, {1, 2}={2, 1}

(続く)

*1:「クリーネ」とカタカナ書きすることが多いけど、「クリーン」のほうが原音に近いという説もある。