モノイドからモナドを作る - 檜山正幸のキマイラ飼育記 (はてなBlog)

モニャドセミナー3をやってから一週間以上経過しちゃったんですが、だいぶ遅れた補足です。なぜ補足が必要かというと、当日の後半、なにかに憑かれてラリラリだったから。ホワイトボードでの説明でグダグダだったところを少しはクリアにしよう、と。説明のストーリーや記号法は、セミナー当日のものとほぼ同じにしました。そのため、慣用の記法とは少しずれたところがあります。例えば、「μ」を使うところで「δ」を使ったりとか。

この記事は、あまり実例がなくて定義ばっかりの印象かもしれませんが、モニャドセミナーが事例中心だから、いいとしましょう。それと、やっぱりどっかで定義を確認することは必要なんです。確認作業では、つまんないタルイ計算が続きますが、我慢してヤッテ。

内容：

モノイドの復習
直積による掛け算関手
掛け算関手の繰り返し適用
2回適用を1回につぶす自然変換δ
クライスリ結合
クライスリ圏

●モノイドの復習

Aがモノイドだとします。ちゃんと言えば、集合Aと二項演算△:A×A→A、単位 u∈A の組(A, △, u) がモノイドですね。{*} を単元集合（singleton set）として、p(*) = u で定義される写像 p:{*}→A も定義しておきます。圏論の言葉でいえば、モノイドとは対象集合が単元集合 {*} である圏です。a∈A に対して、dom(a) = cod(a) = * です。pは、実は恒等（id）そのもので、△は結合（composition）に他なりません。

圏論の枠内で、特殊な圏としてモノイドを定義しなくても、二項演算と単位を持つ代数系と思っても何ら問題はありません。どんな定義／定式化であっても、次の計算法則（公理）は要求します。

(a△b)△c = a△(b△c)
u△a = a△u = a

以下では、二項演算 a△b を、関数形式で △(a, b) と書くこともあるので注意してください。

モノイドの例としては、自然数の足し算とか掛け算とかがあります。足し算の単位は0、掛け算の単位は1です。文字列やリストは、連接演算と空列を伴ってモノイドになります。

ここで先走って言ってしまうと、モノイドがあると自動的にモナドが作れます。自然数または整数の足し算モノイドからはカウンターモナドが作られます（「世界で一番か二番くらいにやさしい「モナド入門」」参照）。文字列の連接モノイドからは、テキストファイルへの出力モナドが出来ます。右自明モノイドと左自明モノイドがそれぞれ、破壊的代入モナドと単一代入モナドに対応することは、「単一代入のモノイド、スタンピングモナド、モナド工場」で述べました。

●直積による掛け算関手

いま、モノイドA（正確には (A, △, u)）を固定します。集合圏Set上の関手Fを次のように定義します。

Fの対象パート F_obj(X) = X×A
Fの射パート F_mor(f:X→Y) = (f×A:X×A→Y×A)

f×A はよく使われる書き方ですが、ちょっと奇妙な感じですよね；写像と集合を掛け算してますから。これは次の意味で使います。

(f×A)(x, a) = (f(x), a)

実は、f×g という書き方があって、f:X→Y, g:S→T に対して次のように定義されます。

f×g:X×S→Y×T
(f×g)(x, s) = (f(x), g(s))

この定義をもとに考えると、f×A は、 f×id_A の略記ということになります。id_AをAと書いてしまうのはけっこう便利で、僕はしょっちゅう使っています。「圏論番外：横着者のための型なし圏論（ただしフォーマル）」に合理化つうか言い訳が書いてあります。

さて、上のF_obj、F_morで定義されるFが、実際に関手になっていることを確認してください。確認すべきことは：

F(dom(f)) = dom(F(f))
F(cod(f)) = cod(F(f))
F(id(X)) = id(F(X))
F(f;g) = F(f);F(g)

もっと噛み砕くと：

dom(f)×A = dom(f×A)
cod(f)×A = cod(f×A)
id(X)×A = id(X×A)
(f;g)×A = (f×A);(g×A)

f×A の定義を参照しながら、id(X) = id_X が実際にXの恒等写像である点に注意すれば示せるでしょう。3番目だけやってみると：



任意の (x, a)∈X×A に関して
  (id(X)×A)(x, a) 

  = (id(X)(x), a)

  = (x, a)
  id(X×A)(x, a)

  = (x, a)
よって、

 id(X)×A = id(X×A)

関手 F' を次のように定義しても同様の結果になります。F'は「左からAを掛ける関手」です。

F'の対象パート F'_obj(X) = A×X
F'の射象パート F'_mor(f:X→Y) = (A×f:A×X→A×Y)

●掛け算関手の繰り返し適用

FとF'の定義から、次は明らかでしょう。

F(F(X)) = (X×A)×A、
F(F(f:X→Y)) = (f×A)×A
F'(F'(X)) = A×(A×X)
F'(F'(f:X→Y)) = A×(A×f)

今まで、Aは単なる集合として扱い、Aがモノイドであること（つまり、△やuの存在）を使わなかったのですが、FまたはF'の2回繰り返し適用を1回適用に“つぶす”ためにΔを使い、XをF(X)に埋め込むためにp（pはuをpointingする写像）を使います。

「F(F(X)) を F(X) につぶす」手順は次のとおり。

まず、 (X×A)×A、≒ X×(A×A) という同型で、F(F(X)) = X×(A×A) とみなす。
X×(A×A) から X×A への写像 X×△ を考える。
(X×△)(x, (a, b)) = (x, △(a, b)) = (x, a△b)
この X×△ は、F(F(X)) から F(X) への写像になっている。

Xごとに決まる X×△ が自然変換であることは、具体的に写像を追いかければわかります（えっ? モニャド3で自然変換すっかり飛ばしたってか。そうでした）。まーとりあえず、次の図式を追いかけて、左上から時計回りでも反時計回りでも同じ結果であることを確認してください。



              f×(A×A)

(x, (a, b)) |----------> (f(x), (a, b))

   ---                      ---

    |                        |

    |つぶす                  |つぶす

    |                        |

    v          f×A          v

 (x, a△b) |----------->  (f(x), a△b)

●2回適用を1回につぶす自然変換δ

前節で、「X×△ は、F(F(X)) から F(X) への写像になっている」と述べました。ここに出てくるXは任意の集合なので、Xを決めるごとに X×△:F(F(X))→F(X) が決まります。別な言い方をすると、集合Xでパラメータ付けられた射の束（index family of morphisms）です。この事実は、X×△が自然変換の定義の半分を満たしていることを示します。実際、X×△は自然変換なんです、すぐ下でそれを示します。

自然変換は、習慣的にギリシャ小文字で書かれるので、X×△をδで表し、パラメータXは下付き添字にします。つまり、X×△ = δ_X。文字δ＜デルタ＞を選んだ理由は、△と形が似ているからです。通常の習慣ではμ＜ミュー＞がよく使われます。

δ_X:F(F(X))→F(X)

F(X) = X×A、F(F(X)) = (X×A)×A だったので、露骨に書き下せば：

δ_X:(X×A)×A→X×A
δ_X((x, a), b)|→(x, a△b)

((x, a), b)←→(x, (a, b)) という対応と前節の可換図式を考慮すれば、次の可換図式が得られます。



            FF(f)

    FF(X) -----------> FF(Y)

      |                 | 

      |                 |

δ_X  |                 | δ_Y

      |                 |

      v     F(f)        v

     F(X) -----------> F(Y)

以上からδが、δ::FF⇒F:Set→Set という自然変換であることがホントにわかりました。

モナドの定義を仮定しちゃって話しますが； IをSetの恒等関手として、ε_X:I(X)→F(X) を、p:{*}→A を元にして作れるので、自然変換 ε::I⇒F:Set→Set も存在します。いまモナド法則の確認はしませんが、(F, δ, ε)の3つ組がモナドを構成します。F, δ, ε は、モノイドの A, △, u から作られています。

●クライスリ結合

X, Yが集合として、f:X→F(Y) の形の射（集合圏の話ですから普通の写像です）をクライスリ射と呼びましょう。F(Y) = Y×A なので、f:X→Y×A です。クライスリ射fを成分表示して、f(x) = (f1(x), f2(x)) とします。これは、f1:X→Y, f2:X→A として f = <f1, f2> というデカルト・ペアリングです。f1が純計算部分、f2が副作用部分と考えるといいでしょう。

g:Y→F(Z) が別なクライスリ射だとして、g1:Y→Z, g2:Y→A はその成分表示。純計算部分どおしは、f1;g1 として結合ができます。しかし、副作用部分まで含めての結合はこのままではうまくいきません。

そこで、g全体に掛け算関手Fを作用させてみると、F(g) = g×A : Y×A→(Z×A)×A となります。F(g)の具体的な表示は次のよう。

(F(g))(y, a) = (g×A)(y, a) = (g(y), a) = ((g1(y), g2(y)), a)

((g1(y), g2(y)), a) を、入れ子を平坦化した (g1(y), g2(y), a) と同一視することがあります。念のため F(g) の展開公式を、タプルを平坦化した形でもう一度書いておくと：

(F(g))(y, a) = (g1(y), g2(y), a)

さてと、fとF(g)は普通に結合できて、具体的な表示は以下のとおり。



  (f;F(g))(x)

  // ; の定義を使って変形

  = F(g)(f(x)) 

  // ｆを成分表示する

  = F(g)(f1(x), f2(x))

  // F(g) の展開公式で展開

  = (g1(f1(x)), g2(f1(x)), f2(x))

以上から、f:X→Y×A, g:Y→Z×A に対して、f;F(g):X→(Z×A)×A が決まります。δ_Z = Z×△ を使うと、(Z×A)×A を Z×A に“つぶせる”ので、f;F(g);δ_Z のプロファイル（域と余域）は、X→Z×A です。f;F(g);δ_Z を f#g と略記することにしましょう。

今までの計算を振り返れば、f#g の露骨な表示は次のとおり。

(f#g)(x) = (g1(f1(x)), g2(f1(x))△f2(x))

新しい演算 # をクライスリ結合と呼びます。f#g は、2つのクライスリ射f, gのクライスリ結合（の結果）です。

クライスリ結合した結果の第一成分、つまり純計算部分だけを取り出すと、g1(f1(x)) = (f1;g1)(x) なので、普通の関数合成になっていることに注目してください。クライスリ射の第二成分が見えない、あるいは無視する状況では純関数計算をしていることになるわけです。別な言い方をすると、純粋計算を保存したまま、副作用部分を付け加えた不純(?)計算がクライスリ結合で定式化できたのです。

●クライスリ圏

ここからは大急ぎ ^^; モノイド (A, △, u) があると、(-)×A または A×(-) という直積掛け算関手が定義できます。この関手をそれぞれ F（右から掛け算）、F'（左から掛け算）とします。それだけではなくて、△とuを使って2つの自然変換を構成できます。

δ::FF⇒F:Set→Set
ε::I⇒F:Set→Set

Fとδを組み合わせて、新しい結合演算 # を定義しました。id'_X = ε_X とすると、新しい恒等を定義できます。

id'_X: X→F(X)

f, g, h などをクライスリ射、つまり集合圏で X→F(Y) の形の射（写像）とすると、今までの定義を参照しながらシコシコ計算すれば、次が確認できます。

(f#g)#h = f#(g#h)
id'_X;f = f;id'_Y = f

これらの事実から、新しい圏が構成されていることがわかります。新しい圏のデータは次のとおりです。

対象：集合
射：クライスリ射： X→F(Y) の形の写像
域：X→F(Y) の域はX
余域：X→F(Y) の余域はY
恒等：id'_X = ε_X
結合： f#g = f;F(g);δ_Z

モノイドが1つあれば、対応するモナドが作れます。モナドがあればクライスリ圏を作れます。つまり、モノイドを探せば、自動的に圏の実例も手に入るのです。ただし、すべてのモナドがモノイド起源ではありません。例えばリストモナドは、モノイドから構成したものではありません。それでもクライスリ圏は作れます。さー、楽しいクライスリ圏を探してみましょう。