モノイドと関数合成

～モナドを理解するための Hors-d'oeuvre として～

モノイド

集合 $S$ と二項演算 $\cdot$ が以下の規則を満たす時、２つ組 $(S,\cdot)$ をモノイド (monoid) という

1. 左結合律: $^{\forall a,b,c\in S}\ [a\cdot b\cdot c=(a\cdot b)\cdot c]$
2. 右結合律: $^{\forall a,b,c\in S}\ [a\cdot b\cdot c=a\cdot (b\cdot c)]$
3. 左単位元: $^{\exists e,\forall x,y\in S}\ [e\cdot y = y]$
4. 右単位元: $^{\exists e,\forall x,y\in S}\ [x\cdot e = x]$

注: 式の左側に書いてあるちっこいのは述語論理の記号

• $\forall a\in S$: 集合 $S$ に属する任意の $a$ に対して右の式が成り立つ
• $\exists e,\forall a\in S$: 集合 $S$ に属する、ある $e$ を定めると、任意の $a$ に対して右の式が成り立つ

関数の合成とモノイド

モノイドの要件に使われた文字を関数らしく書き換えよう
関数の集合 $F$ と合成 $\circ$ は以下の規則を満たす

1. 左結合律: $^{\forall f,g,h\in F}\ [f\circ g\circ h=(f\circ g)\circ h]$
2. 右結合律: $^{\forall f,g,h\in F}\ [f\circ g\circ h=f\circ (g\circ h)]$
3. 左単位元: $^{\exists {\rm id}_左,\forall f,g\in F}\ [{\rm id}_左\circ g = g]$
4. 右単位元: $^{\exists {\rm id}_右,\forall f,g\in F}\ [f\circ {\rm id}_右 = f]$

ただし、ここで出てきている関数は合成可能なように型を合わせる必要がある
すなわち、以下のようになる

• $f:V\to W$
• $g:U\to V$
• $h:T\to U$
• ${\rm id}_左:V\to V$
• ${\rm id}_右:T\to T$