斜めの線を使わない圏論(2) - エレファント・ビジュアライザー調査記録

まだ圏論の詳しい説明に入っていませんがしばらくこのまま続けます。自由群の説明ができるぐらいまでなんとか数式で説明していきたいのですが、どこまでできるか調べているところです。

直積と直和(圏論の用語では積と余積)で作られた以下の集合を考えます。

$X^* = 1 + X + X^2 + X^3 + \cdots$

これに $(x_1, x_2, \cdots , x_m) \in X^m$ と $(y_1, y_2, \cdots , y_n) \in X^n$ の積を $(x_1, x_2, \cdots , x_m, y_1, y_2, \cdots , y_n) \in X^{m+n}$ とする演算を定義すると $X$ で生成された自由モノイドになります。

次にHaskellなどの代数的データ型について考えます。たとえばリストは以下のような定義になります。
data List a = Nil | Cons a (List a)
直積と直和を使って再帰的に書くと $\mathrm{List}(X) = 1 + X \times \mathrm{List}(X)$ と書くことができて構築子
$\mathrm{Nil}: 1 \to \mathrm{List}(X)$
$\mathrm{Cons}: X \times \mathrm{List}(X) \to \mathrm{List}(X)$
で自由生成されたものと考えることができます。非再帰的に書くと
$\mathrm{List}(X) = 1 + X + X^2 + X^3 + \cdots$
のようになると考えられます。これは上記の $X^*$ と同様 $X$ で生成された自由モノイドとなります。

[問題2] $\mathrm{List}(X)$ と $X^*$ の関係は？

$X^*$ の中の直積は結合的であっても結合的でなくても良かったのですが、リストの元の定義では非結合的だと考えられます。この場合リストの書き方を変えて
$\mathrm{List}(X) = [] + [X] + [X, X] + [X, X, X] + \cdots$
と書くことにします。モノイドの演算はリストの用語ではappendと呼ばれるものなります。構築子による構成と分解で書くことができて
$\mathrm{append}([], y) = y$
$\mathrm{append}([x|w], y) = [x|\mathrm{append}(w, y)]$
となります。 $[]$ は $\mathrm{Nil}$ 、 $[|]$ は $\mathrm{Cons}$ の構成と分解を表します。

[問題3] 構成と分解を代数的構造として表すと？

モノイド圏というものもありますが、これはまだ調べていません。

[問題4] 直積と直和で作られた代数的構造と随伴関手の関係は？

関数プログラミングでは構築子の分解による場合分けができることがあります。これは関数プログラミングの一部なのかよくわかりません。Prologやラムダ計算の理論にありそうです。一般の場合分けを構築子の分解で表すことができるのかもわかりません。

[問題5] 構築子による場合分けの一般論は？

オブジェクト指向プログラミングの場合はクラスによって場合分けができますがこれと代数的データ型の関係はどうなるのかという問題があります。LispとSmalltalkを比較してみると、Lispにはリストという1つのクラスしかなく場合分けを明示的に書かなければいけないものと考えることもできます。

オブジェクト指向プログラミングのクラスを直積と直和と同じ情報を持ち構成と分解ができるように書くことができます。この場合は代数的データ型と同じものと考えられます。構築子の構成はコンストラクター、分解はクラスで行うことができます。分解によって場合分けができるということがオブジェクト指向プログラミングの特徴になっています。C# のクラスを使って書こうと思いましたが複雑なので難しいです。

オブジェクト指向プログラミングの特徴として情報隠蔽(カプセル化)があります。情報隠蔽によってデータを代数的に扱うことができます。代数的データ型は基本的には直積と直和しか扱わないようなのでこれとは違うのですが、どのような違いがあるのか考えてみたいと思います。

[問題6] クラスと代数的データ型の関係は？

続いてオブジェクト指向プログラミングとイベント駆動型プログラミングについて考えていきます。イベント駆動型プログラミングではプログラムはイベントを待機する部分とイベントを処理する部分に分かれています。オブジェクト指向のオブジェクトが変更可能であるため関数プログラミング的機能によってイベントの処理を記述することができるということがオブジェクト指向プログラミングの特徴と考えられます。SmalltalkでGUIを記述するときそうなっていたため(？)オブジェクト指向が使われるようになったと考えられます。

オブジェクト指向のプログラミング言語(C#など)では関数プログラミング的な機能が使える場合があります。その機能によってライブラリを共通化することができますが、オブジェクト指向のライブラリの中にどのように組み込むのか考えなくてはいけません。

[問題7] 関数プログラミング的機能と変更可能なオブジェクトの関係は？

イベントを待機するプログラムが無限の時間にわたって動作すると考えた場合、イベントを処理するプログラムを関数プログラミング的機能によって記述したときそれをプログラム全体で考えたときどうなるのかを考える必要があります。(参照透過性を持つような)関数プログラミング的機能によって記述されたプログラムの組み合わせによって、無限に動作するプログラムを記述する方法を考えていきたいと思います。組み合わせ方を代数的に表す方法を考えます。

[問題8] 無限に動作するプログラムの代数的構造は？

以上のような問題を記述するため圏論について調べていきます。