プログラミングから見た圏論

前置き

“お行儀の良い”関数型プログラミング言語^[1]があるとします。
型を対象とし、射を関数とし、射の等しさを関数の外延的な等しさとし、射の合成を関数合成とし、恒等射を恒等関数とするとこれは圏を成します。

この事実は、圏論を使ってプログラミングを説明するときに大いに役立ち、プログラミングについての理解を深めることができます。

本記事では、その逆を目的としています。
つまり、プログラミングの知識を圏論の理解に役立てようという趣旨です。

関数合成と恒等関数

プログラミングでは関数合成と恒等関数を定義することができます。

関数合成は2つの関数を引数に取り、関数を返す操作です。
関数合成は一方の終域と他方の始域が一致している場合にのみ定義されます。
関数 $ff$ と $gg$ の合成を $g∘fg \circ f$ と書きます。
$f:A→Bf : A → B$ と $g:B→Cg : B → C$ のとき、$g∘fg \circ f$ の型は $A→CA → C$ です。
合成関数は任意の $x:Ax : A$ について $ff$ を適用した後に $gg$ を適用したものを返します。

_∘_ : (B → C) → (A → B) → (A → C)
g ∘ f = λ a → g (f a)

本記事では $x:Ax : A$ に関数 $f:A→Bf: A → B$ を適用した結果を $f(x)f(x)$ ではなく $f xf \space x$ と書くので注意してください。

恒等関数 $funcidX\mathrm{funcid}_{X}$ は任意の型 $XX$ に対して定義できる関数で、その型は $X→XX → X$ です。
恒等関数は任意の要素 $a:Xa : X$ に対してそのまま $aa$ を返します。

funcid : X → X
funcid = λ a → a

2つの関数 $f:A→Bf : A → B$ と $g:A→Bg : A → B$ について、任意の入力 $x:Ax : A$ に対する出力 $f xf \space x$ と $g xg \space x$ が常に一致するとき、$ff$ と $gg$ は外延的に等しいと言います。
本記事では、関数に対して $f=gf = g$ と書くときは外延的な等しさを意味することとします。

圏

圏の定義も念のため書いておきます。

圏は射と呼ばれる“何か”がいくつかの性質を満たすもののことを言います。
射は対象と呼ばれる“何か”を2つ持ち、一方を射の域、他方を射の余域と言います。
任意の対象 $AA$ と $BB$ について、$AA$ を域、$BB$ を余域とする射を「$AA$ から $BB$ への射」と言います。
$ff$ が $AA$ から $BB$ への射であることを $f:A⇒Bf : A ⇒ B$ と書くことにします。
※記号 $⇒⇒$ を用いる表記はあまり一般的ではなく、通常は $f:A→Bf : A → B$ と書くことが多いと思いますが、本記事では記号 $→→$ を関数を表す記号として留保します。

$AA$ から $BB$ への射は一般に複数存在するので、便宜上それ全体を表す用語が欲しいです。
ここではそれを$AA$ から $BB$ へのホムと呼び、$A⇒BA ⇒ B$ と書きます。

2つの射は、同じホムに属している場合に限り、その“等しさ”が定義されます。
言い換えると、その域が一致し、かつその余域も一致するときに定義されます。
域や余域が異なる場合、射の等しさは考えません。
「2つの射が等しいとは何か？」は圏を定義するときに決めます。^[2]
$ff$ と $gg$ が等しいとき、$f=gf = g$ と書きます。

射には合成と呼ばれる演算 $(−∘−)(- \circ -)$ が定義されます。
これは2つの射を受け取り、射を返す操作です。
射の合成は一方の余域と他方の域が一致している場合は必ず定義されますし、射の合成が定義されるのはそのときに限ります。
射 $f:A⇒Bf : A ⇒ B$ と $g:B⇒Cg : B ⇒ C$ の合成を $g∘fg \circ f$ と書きます。
これは $g∘f:A⇒Cg \circ f : A ⇒ C$ です。

射の合成は以下の性質を満たさなければなりません。
任意の射 $f:A⇒Bf : A ⇒ B$, $g:B⇒Cg : B ⇒ C$, $h:C⇒Dh : C ⇒ D$ に対して

$$(h∘g)∘f=h∘(g∘f) (h \circ g) \circ f = h \circ (g \circ f)$$

が成り立ちます。
これを射の合成の結合則と言います。
※ここで射の等しさを論じていますが、左辺の射と右辺の射のホムが一致するのでその等しさを議論しても問題ありません。

域と余域が一致する任意のホム $A⇒AA ⇒ A$ は恒等射と呼ばれるある特別な射を持たなければなりません。
これを $idA\mathrm{id}_{A}$ と書きます。
恒等射は任意の $f:A⇒Bf : A ⇒ B$ について以下の性質を満たします。

$$f∘idA=f=idB∘f f \circ \mathrm{id}_{A} = f = \mathrm{id}_{B} \circ f$$

射はホムの単なる要素である

プログラミングの観点からすると、射 $f:A⇒Bf : A ⇒ B$ は、ホム $A⇒BA ⇒ B$ の単なる要素に過ぎません。

関数の場合、$AA$ の要素 $xx$ に関数 $f:A→Bf : A → B$ を適用して $BB$ の要素 $f xf \space x$ を得ることができます。
しかし、射 $f:A⇒Bf : A ⇒ B$ に対してできることは射の合成だけです。

射の合成は単なる2引数関数である

プログラミングの観点からすると、射の合成は2つの射を引数にとり、射を返す関数に過ぎません。

任意の対象 $AA$, $BB$, $CC$ について以下の関数

$$(−∘−):(B⇒C)→(A⇒B)→(A⇒C) (- \circ -) : (B ⇒ C) → (A ⇒ B) → (A ⇒ C)$$

が定義されます。
圏を定義するときは、上記関数を“実装”しなければなりません。

射の後合成

射の合成 $(−∘−)(- \circ -)$ に $g:B⇒Cg : B ⇒ C$ を部分適用してみましょう。

$$(g∘−):(A⇒B)→(A⇒C) (g \circ -) : (A ⇒ B) → (A ⇒ C)$$

これは任意の射 $f:A⇒Bf : A ⇒ B$ について、それを $gg$ で合成した結果 $g∘fg \circ f$ を返す関数です。
これを $gg$ による後合成関数と呼び、$(g∘−)(g \circ -)$ や $postg\mathrm{post}^{g}$ と書くことにします。
後合成関数は射の余域を変更します。

ここでの興味深い観察は、$g:B⇒Cg : B ⇒ C$ が引数の射の余域 $BB$ と結果の射の余域 $CC$ を指定していますが、域 $AA$ については何も指定しないということです。
つまり、$postg\mathrm{post}^{g}$ は各対象 $AA$ について定義されるジェネリック関数です。
$AA$ の恒等射を $idA\mathrm{id}_{A}$ と書く流儀に倣って $postAg\mathrm{post}^{g}_{A}$ とでも書くべきでしょう。

同様に、後合成関数 $(g∘−)(g \circ -)$ の引数となる射の始域 $AA$ を明示したい場合は $(g∘−A)(g \circ -_{A})$ と書くことにします。

射の前合成

同様に、射の合成 $(−∘−)(- \circ -)$ を flip してから $f:A⇒Bf : A ⇒ B$ を部分適用することにより、射の前合成

$$preCf:(B⇒C)→(A⇒C) \mathrm{pre}^{f}_{C} : (B ⇒ C) → (A ⇒ C)$$

を考えることもできます。

本記事では割愛しますが、後合成と同じような議論が展開できます。^[3]

後合成の性質

射 $g:B⇒Cg : B ⇒ C$ があるとき、その後合成を考えることで射から射への関数 $(A⇒B)→(A⇒C)(A ⇒ B) → (A ⇒ C)$ を生成することができました。
逆に、射から射への関数 $(A⇒B)→(A⇒C)(A ⇒ B) → (A ⇒ C)$ があるときに、これが何らかの射の後合成と見なせるための条件とは何でしょうか。

つまり、関数 $αA:(A⇒B)→(A⇒C)α_{A} : (A ⇒ B) → (A ⇒ C)$ があるとき、ある射 $g:B⇒Cg : B ⇒ C$ を用いて $αA=postAgα_{A} = \mathrm{post}^{g}_{A}$ と書ける^[4]ための条件とは何でしょうか。

自然性

任意の対象 $zz$ について関数 $αz:(z⇒B)→(z⇒C)α_{z} : (z ⇒ B) → (z ⇒ C)$ が定義されているとします。

任意の対象 $xx$ と $yy$ および、任意の射 $p:y⇒xp : y ⇒ x$ と $h:x⇒Bh : x ⇒ B$ を考えます。

初期設定

このとき、$y⇒Cy ⇒ C$ の射を得る方法が2通りあるので考えてみてください。

---

まず1つ目の方法です。

$hh$ に関数 $αxα_{x}$ を適用することで $x⇒Cx ⇒ C$ の射が得られます。
以下の図では細い矢印が射を、太い矢印が関数適用を表します。

$αxα_{x}$ の適用

射の合成を考えることで $y⇒Cy ⇒ C$ の射が得られます。

$pp$ の前合成

続いて2つ目の方法です。
初期設定に戻り、今度は先に $pp$ と $hh$ を合成します。

射の合成

これに関数 $αyα_{y}$ を適用することで $y⇒Cy ⇒ C$ の射が得られます。
ここで、$αα$ を適用する射の始域が1つ目の方法とは異なる点に注意してください。

$αyα_{y}$ の適用

以上により、$y⇒Cy ⇒ C$ の2つの射が得られました。

• 関数を適用した後に射を合成する $(αx h)∘p(α_{x} \space h) \circ p$
• 射を合成した後に関数を適用する $αy (h∘p)α_{y} \space (h \circ p)$

もし、関数 $αα$ が何らかの射の後合成として見なせるとき、何が言えるでしょうか。
ある射 $g:B⇒Cg : B ⇒ C$ が存在して、$αz=postzgα_{z} = \mathrm{post}^{g}_{z}$ を満たすとして、先ほどの図を書き直してみます。

初期設定

太矢印で書いていた関数 $αzα_{z}$ の適用の箇所を、すべて $gg$ の後合成で書き換えることができます。

$αα$ を $gg$ の後合成で書き換える

射の合成の結合則により、$(g∘h)∘p=g∘(h∘p)(g \circ h) \circ p = g \circ (h \circ p)$ が成り立ちます。
したがって、もし関数 $αzα_{z}$ が何らかの射の後合成と見なせるのであれば、先ほど作った2つの射は等しくなければなりません。

$$(αx h)∘p=αy (h∘p) (α_{x} \space h) \circ p = α_{y} \space (h \circ p)$$

式変形をしてこの条件を少し書き換えてみましょう。

ここで左辺を式変形すると

$$(αx h)∘p=((αx h)∘−y) p \begin{aligned} (α_{x} \space h) \circ p &= ((α_{x} \space h) \circ -_{y}) \space p \end{aligned}$$

となり、右辺を式変形すると

$$αy (h∘p)=αy ((h∘−y) p)=(αy∘(h∘−y)) p \begin{aligned} α_{y} \space (h \circ p) &= α_{y} \space ((h \circ -_{y}) \space p) \\ &= (α_{y} \circ (h \circ -_{y})) \space p \\ \end{aligned}$$

となるので

$$((αx h)∘−y)=αy∘(h∘−y) ((α_{x} \space h) \circ -_{y}) = α_{y} \circ (h \circ -_{y})$$

とも書けます。^[5]

読むとすれば「$hh$ に $αxα_{x}$ を関数適用して得られる射の後合成と、$hh$ を後合成してから $αyα_{y}$ を関数適用して得られる射から射への関数は外延的に等しい」となるでしょう。

ちなみに、同様の式変形を行うことで今度は前合成の観点から成り立つ性質を得ることができます。

$$(−∘p)∘αx=αy∘(−∘p) (- \circ p) \circ α_{x} = α_{y} \circ (- \circ p)$$

関数 $αzα_{z}$ は任意の前合成について可換です。

以上が、関数 $αzα_{z}$ を何らかの射の後合成と見なすための必要条件となります。

後合成関数から見た射

先ほどの条件

$$((αx h)∘−y)=αy∘(h∘−y) ((α_{x} \space h) \circ -_{y}) = α_{y} \circ (h \circ -_{y})$$

では、射の合成を直接には使用していない点に注意してください。
後合成 $(g∘−)(g \circ -)$ を単なる関数と見なし、$postg\mathrm{post}^{g}$ のほうで書くと分かりやすいかもしません。

$$postyαx h=αy∘postyh \mathrm{post}^{α_{x} \space h}_{y} = α_{y} \circ \mathrm{post}^{h}_{y}$$

ここで射の合成という概念を忘れ、代わりに射 $gg$ の後合成と呼ばれる特別な関数 $postxg:(x⇒B)→(x⇒C)\mathrm{post}^{g}_{x} : (x ⇒ B) → (x ⇒ C)$ の存在を直接仮定したとして、圏の性質を言い換えることができます。

合成射の後合成は、個別の射の後合成の関数合成で言い換えることができます。

$$postzg∘f=postzg∘postzf \mathrm{post}^{g \circ f}_{z} = \mathrm{post}^{g}_{z} \circ \mathrm{post}^{f}_{z}$$

恒等射の後合成は元の射を変えないので、単なる恒等関数になります。

$$postAidB=funcidA⇒B \mathrm{post}^{\mathrm{id}_{B}}_{A} = \mathrm{funcid}_{A ⇒ B}$$

射の構成

では実際に、任意の対象 $zz$ に対して定義されている関数 $αz:(z⇒B)→(z⇒C)α_{z} : (z ⇒ B) → (z ⇒ C)$ が、任意の対象 $xx$ および $yy$ と任意の $h:x⇒Bh : x ⇒ B$ について条件

$$((αx h)∘−y)=αy∘(h∘−y) ((α_{x} \space h) \circ -_{y}) = α_{y} \circ (h \circ -_{y})$$

を満たすとき、何らかの射 $g:B⇒Cg : B ⇒ C$ が存在して

$$αz=postzg α_{z} = \mathrm{post}^{g}_{z}$$

が成り立つようにできるでしょうか。

$B⇒CB ⇒ C$ の射を生成するために、$αB:(B⇒B)→(B⇒C)α_{B} : (B ⇒ B) → (B ⇒ C)$ を考えます。
恒等射 $idB\mathrm{id}_{B}$ に適用すると $B⇒CB ⇒ C$ の射が得られます。これを $g′g'$ とおきます。

$$g′:B⇒Cg′=αB idB \begin{aligned} &g' : B ⇒ C \\ &g' = α_{B} \space \mathrm{id}_{B} \\ \end{aligned}$$

このとき、$g′g'$ の後合成を考えてみましょう。
射 $g′g'$ は関数 $αBα_{B}$ の適用により定義されているので、射の合成と関数適用の順番を交換できるはずです。

$$postzg′=(g′∘−z)=((αB idB)∘−z)=αz∘(idB∘−z)=αz∘funcidz⇒B=αz \begin{aligned} \mathrm{post}^{g'}_{z} &= (g' \circ -_{z}) \\ &= ((α_{B} \space \mathrm{id}_{B}) \circ -_{z}) \\ &= α_{z} \circ (\mathrm{id}_{B} \circ -_{z}) \\ &= α_{z} \circ \mathrm{funcid}_{z ⇒ B} \\ &= α_{z} \end{aligned}$$

以上により、関数 $αzα_{z}$ がまさに射 $g′g'$ の後合成と外延的に等しいということが示されました。

射の合成の便利さ

以上の観察の結果を踏まえると、圏における“射の合成”の概念の便利さが見えてきます。

圏は射の合成の結合性と恒等射の存在を要求するので、これにより

$$((αx h)∘−y)=αy∘(h∘−y) ((α_{x} \space h) \circ -_{y}) = α_{y} \circ (h \circ -_{y})$$

を満たすような関数 $αzα_{z}$ があるとき、それを射の後合成と見なせるような射 $αB idBα_{B} \space \mathrm{id}_{B}$ が必ず存在します。

逆に、そのような性質を満たす関数のことを、単なる射の後合成として書くことができるわけです。
もし射の合成の概念を忘れてしまい、射の後合成を射から射への関数で記述しなければならなくなったとすると、上記の条件を至るところで要求しなければなりません。

また、射から射への関数の関数合成の話を、単なる射の合成に帰着できるのも便利な点です。
これは

$$(g∘−)∘(f∘−)=((g∘f)∘−) (g \circ -) \circ (f \circ -) = ((g \circ f) \circ -)$$

が成り立つからです。

同型射

この流れで同型射を言い換えてみます。

2つの射 $f:A⇒Bf : A ⇒ B$ と $g:B⇒Ag : B ⇒ A$ が

$$g∘f=idAf∘g=idB \begin{aligned} g \circ f &= \mathrm{id}_{A} \\ f \circ g &= \mathrm{id}_{B} \\ \end{aligned}$$

を満たすとき、$ff$ と $gg$ は同型射であると言います。
2つの対象の間に同型射が存在するとき、それらを同型であると言い、$A≅BA \cong B$ と書きます。
圏論の言葉で書くと非常に簡潔ですね。

ところで、これらの条件が成り立つとき、任意の $h:x⇒Ah : x ⇒ A$ と $h′:y⇒Bh' : y ⇒ B$ について

$$g∘f∘h=hf∘g∘h′=h′ \begin{aligned} g \circ f \circ h &= h \\ f \circ g \circ h' &= h' \\ \end{aligned}$$

が成り立つので、以下のように書けます。

$$(g∘−x)∘(f∘−x)=funcidx⇒A(f∘−y)∘(g∘−y)=funcidy⇒B \begin{aligned} (g \circ -_{x}) \circ (f \circ -_{x}) &= \mathrm{funcid}_{x ⇒ A} \\ (f \circ -_{y}) \circ (g \circ -_{y}) &= \mathrm{funcid}_{y ⇒ B} \\ \end{aligned}$$

この事実を使って、同型射の概念を、射の合成を直接使わずに関数の観点から記述してみます。

関数 $αz:(z⇒A)→(z⇒B)α_{z} : (z ⇒ A) → (z ⇒ B)$ が存在して、条件

$$((αx h)∘−y)=αy∘(h∘−y) \begin{aligned} ((α_{x} \space h) \circ -_{y}) = α_{y} \circ (h \circ -_{y}) \\ \end{aligned}$$

を満たすとし、同様に関数 $βz:(z⇒B)→(z⇒A)β_{z} : (z ⇒ B) → (z ⇒ A)$ が存在して条件

$$((βx h)∘−y)=βy∘(h∘−y) \begin{aligned} ((β_{x} \space h) \circ -_{y}) = β_{y} \circ (h \circ -_{y}) \\ \end{aligned}$$

を満たすとします。更にこれらの関数合成の結果は恒等関数と外延的に等しくなるとします。

$$βx∘αx=funcidx⇒Aαy∘βy=funcidy⇒B \begin{aligned} β_{x} \circ α_{x} &= \mathrm{funcid}_{x ⇒ A} \\ α_{y} \circ β_{y} &= \mathrm{funcid}_{y ⇒ B} \\ \end{aligned}$$

このとき、関数 $αzα_{z}$ と $βzβ_{z}$ を用いて同型射を復元できるでしょう。

したがって、そのような $αα$ と $ββ$ が存在することを以って $A≅BA \cong B$ を言うことができます。

ちなみに、同様の議論が射の前合成でも展開でき、射から射への関数を射の前合成と見なせるための条件や同型射の概念を導出できます。

まとめ

射の後合成が持っている性質と、射から射への関数を射の後合成と見なせるための条件について観察しました。
これに派生して、射から射への関数の存在から同型を言うための条件についても観察しました。

もし本記事が参考になりましたら、いいねあるいはコメントよろしくお願いします。

脚注

1. 正確には、これらが圏を成すようなプログラミング言語を“お行儀の良い”と言うべきでしょう。

2. 射の等しさは同値関係でなければなりません。
   また、射の合成は射の等しさを保存しなければなりません。

3. 実際に確かめてみると分かることですが、後合成と全く同じというわけにはいきません。
   例えば、合成の順番が逆になる箇所があります。

4. 改めて、本記事では等号 $==$ を外延的な等しさの意味で使っている点に注意してください。

5. 右辺の左側の $∘\circ$ は射の合成ではなく関数の合成である点に注意してください。