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

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

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

参照用 記事

あまり見かけないモナドの例

モナドに関して:

  • モナドの単位自然変換は、成分ごとにモノ射だろう。

とか予想しがちですが、これは違います。よく見かけるモノドの単位がモノ射成分なだけです。$`\newcommand{\mrm}[1]{\mathrm{#1}}
\newcommand{\id}{\mathrm{id} }
\newcommand{\In}{\text{ in }}
\newcommand{\twoto}{\Rightarrow }
`$

内容:

有向グラフから完全グラフを作るモナド

有向グラフは、次のような4つ組 $`(V, E, s, t)`$ です。

  • $`V`$ は、頂点の集合
  • $`E`$ は、辺の集合
  • $`s`$ は、辺に始点(始端頂点)を対応させる写像 $`s:E \to V`$
  • $`t`$ は、辺に終点(終端頂点)を対応させる写像 $`t:E \to V`$

2つの頂点を結ぶ辺〈有向辺〉はたくさんあってもいいことに注意してください。

2つの(同じでもいい)有向グラフ $`(V, E, s, t), (V', E', s', t')`$ があるとき、そのあいだの準同型写像は、次のような2つ組 $`(f_v, f_e)`$ (と等式的法則)です。

  • $`f_v`$ は、頂点に頂点を対応させる写像 $`f_v : V \to V'`$
  • $`f_e`$ は、辺に辺を対応させる写像 $`f_e : E \to E'`$
  • 以下の図式が可換になる。

$`\require{AMScd}
\begin{CD}
E @>{f_e}>> E' \\
@V{s}VV @VV{s'}V\\
V @>{f_v}>> V'
\end{CD}\\
\text{commutative in }{\bf Set}\\
\begin{CD}
E @>{f_e}>> E' \\
@V{t}VV @VV{t'}V\\
V @>{f_v}>> V'
\end{CD}\\
\text{commutative in }{\bf Set}
`$

有向グラフ達とそのあいだの準同型写像達は圏を形成するので、その圏を $`{\bf Graph}`$ とします。

与えられた有向グラフ $`(V, E, s, t)`$ に対して、次のような有向グラフ $`(V', E', s', t')`$ を作ります。

  • $`V' := V`$
  • $`E' := V\times V`$
  • $`s' := \pi_1`$ (直積の第一射影)
  • $`t' := \pi_2`$ (直積の第二射影)

次のように書けます。

$`\quad (V', E', s', t') := (V, V\times V, \pi_1,\pi_2)`$

新しく作った有向グラフ $`(V, V\times V, \pi_1,\pi_2)`$ は、もとの有向グラフと同じ頂点を持つ完全有向グラフになります。

有向グラフ $`(V, E, s, t)`$ から有向グラフ $`(V, V\times V, \pi_1, \pi_2)`$ を作る操作は関手に仕立てられます。その関手を $`F: {\bf Graph}\to{\bf Graph} \In {\bf CAT}`$ とします。$`F`$ の射パートは次のようになります。

$`\text{For }(f_v, f_e) : (V, E, s, t) \to (V', E', s', t') \In {\bf Graph}\\
\quad F(\, (f_v, f_e) \,) := (f_v, g_e)\\
\text{Where }\\
\quad (f_v, g_e) : (V, V\times V, \pi_1, \pi_2) \to (V', V'\times V', \pi_1, \pi_2) \In {\bf Grap}\\
\quad \text{For }(v_1, v_2) \in V\times V\\
\qquad g_e(v_1, v_2 ) := (f_v \times f_v)(v_1, v_2) = (f_v(v_1), f_v(v_2)) \;\in V'\times V'
`$

関手の結合〈composition〉と関手と自然変換のヒゲ結合〈whiskering〉の図式順演算子記号は $`*`$ とします(「関手と自然変換の計算に出てくる演算子記号とか // 今後使う予定の演算子記号〉参照)。次の等式が成立します。

$`\quad F*F = F`$

関手のあいだのこの等式は恒等自然変換 $`\mrm{ID}_F`$ なので、恒等自然変換に $`\mu`$ という別名を与えれば、

$`\quad \mu :: F*F \twoto F : {\bf Graph} \to {\bf Graph} \In {\bf CAT}`$

または(同じことですが)、

$`\quad \mu : F*F \to F \In {\bf CAT}({\bf Graph}, {\bf Graph})`$

が成立します。

$`\mu`$ は恒等自然変換なので、次の図式の可換性は自明です。

$`\begin{CD}
F*F*F @>{\mu * \mrm{ID}_F}>> F*F\\
@V{\mrm{ID}_F * \mu}VV @VV{\mu}V\\
F*F @>{\mu}>> F
\end{CD}\\
\text{commutative in }{\bf CAT}({\bf Graph}, {\bf Graph} )
`$

次に、自然変換 $`\eta`$ を定義しましょう。もうお分かりでしょうが、$`\eta`$ はモナドの単位となるべき自然変換です。

$`\quad \eta :: \mrm{Id}_{\bf Graph} \twoto F : {\bf Graph} \to {\bf Graph} \In {\bf CAT}`$

または、

$`\quad \eta : \mrm{Id}_{\bf Graph} \to F \In {\bf CAT}({\bf Graph}, {\bf Graph})`$

です。

$`G = (V, E, s, t)`$ に対して、$`\eta`$ の$`G`$-成分は次のように定義します。

$`\quad \eta_G := (\id_V, g_e) : G \to F(G) \In {\bf Graph}\\
\text{Where }\\
\quad g_e : E \to V\times V\\
\quad \text{For }e \in E\\
\qquad g_e( e ) := (s(e), t(e) ) \;\in V\times V
`$

この定義に基づき次の図式の可換性を示せます。(有向グラフ $`G`$ を代入すると、図式は $`F(G)`$ の恒等写像だけになります。)

$`\begin{CD}
\mrm{Id}_{\bf Graph} * F @>{\eta * \mrm{ID}_F}>> F * F \\
@V{\mrm{ID}_F}VV @VV{\mu}V\\
F @= F
\end{CD}\\
\text{commutative in }{\bf CAT}({\bf Graph}, {\bf Graph})\\
\:\\
\begin{CD}
F * \mrm{Id}_{\bf Graph} @>{\eta * \mrm{ID}_F}>> F * F \\
@V{\mrm{ID}_F}VV @VV{\mu}V\\
F @= F
\end{CD}\\
\text{commutative in }{\bf CAT}({\bf Graph}, {\bf Graph})
`$

以上により、$`(F, \mu, \eta)`$ は圏 $`{\bf Graph}`$ 上のモナドだと分かりました。$`\eta_G`$ がモノ射とは限らないことは、$`G`$ として例えば、頂点が1個で自己ループ辺が2本あるグラフを考えればいいでしょう。

非空集合を一点に潰すモナド

集合圏上のモナドで、もっと過激な例を挙げます。

集合圏上の自己関手 $`K:{\bf Set}\to{\bf Set}\In {\bf CAT}`$ を次のように定義します。

  • 集合 $`X`$ に対して、$`X \ne \emptyset`$ ならば $`K(X) := {\bf 1}`$ ($`{\bf 1}`$ は特定された単元集合)
  • 集合 $`X`$ に対して、$`X = \emptyset`$ ならば $`K(X) := \emptyset`$
  • 写像 $`f:X \to Y`$ に対して、$`K(f): K(X) \to K(Y)`$ は必然的に決まってしまう。

この関手でも次の等式が成立します。

$`\quad K*K = K`$

前節と同様に、恒等自然変換 $`\mrm{ID}_K`$ を $`\mu`$ と置くと、$`\mu`$ はモナド乗法としての結合律を満たします。

自然変換 $`\eta`$ の$`X`$-成分は、

$`\quad \eta_X : X \to K(X)`$

ですが、$`K(X)`$ は単元集合か空集合なので、これも必然的に決まってしまいます。

$`(K, \mu, \eta)`$ は集合圏 $`{\bf Set}`$ 上のモナドになります。$`\eta_X`$ は、$`X = {\bf 1}, X = \emptyset`$ 以外ではモノ射〈単射〉にはならいですね。

このモナドを、僕はクラッシュモナド〈crush monad〉と呼んでます。クラッシュモナドに関わる随伴系〈adjunction〉やクライスリ圏を考えると、意外に面白かったりします。