Kleisli圏
概要
Kleisli圏（Kleisli category）とは、圏 $\mathcal C$ 上のモナド $(T,\eta,\mu)$ に対し、$\mathcal C$ の対象を対象とし、射 $X\to TY$ を $X$ から $Y$ への射とする圏で、恒等射を単位 $\eta_X$、合成を $\mu_Z\circ T(g)\circ f$ で定めたものである。$\mathcal C$ からKleisli圏への関手と、射 $f$ をその延長 $\mu_Y\circ T(f)$ に送る関手は随伴をなし、もとのモナド $T$ を定める。$T$ を定める随伴 $F\dashv G$ のどれに対しても、左右の随伴と可換な関手がKleisli圏からただ一つあって充満忠実になるので、Kleisli圏は $T$ を定める随伴の中で最小のもので、自由代数の圏と見なせる。部分写像の圏や関係の圏がその例である。
前提知識: モナドとBarr–Beckの定理, 随伴関手, 圏, 自然変換
集合 $X$ から集合 $Y$ への「答えが出ないこともある写像」（部分写像）は、普通の写像 $X\to Y\sqcup\{*\}$ と同じものである。「値が一つに決まらず、値の集合を返す写像」は写像 $X\to\mathcal P(Y)$ であり、これは $X$ から $Y$ への二項関係と同じものである。どちらも、圏 $\mathcal C$ 上のモナド $T$ に対し、射 $X\to TY$ を「$X$ から $Y$ への新しい射」とみなす構成の例になっている。新しい射の合成は、$T$ の乗法 $\mu$ を使って「$T$ が二重に付いたものを一重に戻す」ことで定まる。こうしてできる圏を Kleisli 圏 という。
Kleisli 圏は、モナド $T$ を定める随伴のうちで最も小さいものを与える。随伴 $F\dashv G$ が $T$ を定めるとき、Kleisli 圏は $F$ の像にある「自由な対象」とその間の射だけを集めた圏と見なせ、$T$ の代数の圏（Eilenberg–Moore圏）の中では自由代数のなす充満部分圏と見なせる。この記事では、Kleisli 圏が定める随伴とその始対象性（最小性）を証明し、部分写像の圏・関係の圏・自由加群の圏が Kleisli 圏として現れることを確かめる。
定義
圏 $\mathcal C$ 上のモナド $(T,\eta,\mu)$ を固定する。$T\colon\mathcal C\to\mathcal C$ は関手、$\eta\colon\operatorname{Id}_{\mathcal C}\Rightarrow T$（単位）と $\mu\colon TT\Rightarrow T$（乗法）は自然変換で、各対象 $X$ について
$$
\mu_X\circ T(\mu_X)=\mu_X\circ\mu_{TX},\qquad
\mu_X\circ\eta_{TX}=\operatorname{id}_{TX}=\mu_X\circ T(\eta_X)
$$
が成り立つ（モナドとBarr–Beckの定理 の定義「モナド」）。射の合成は $g\circ f$（先に $f$）と書く。
モナド $(T,\eta,\mu)$ の Kleisli 圏（Kleisli category）$\mathcal C_T$ を次で定める。
- 対象は $\mathcal C$ の対象である。
- $X$ から $Y$ への射は、$\mathcal C$ の射 $f\colon X\to TY$ である。$\mathcal C_T$ の射として見るとき $f\colon X\rightsquigarrow Y$ と書く。
- $X$ 上の恒等射は $\eta_X\colon X\to TX$ である。
- $f\colon X\rightsquigarrow Y$ と $g\colon Y\rightsquigarrow Z$ の合成は
$$ g\circ_T f:=\mu_Z\circ T(g)\circ f\colon X\to TY\to TTZ\to TZ $$
である。
定義は Rie16 Definition 5.2.10（p. 194）、Mac98 Chapter VI §5, Theorem 1（p. 147）による。$\mathcal C_T(X,Y)=\mathcal C(X,TY)$ である。$\mathcal C$ の射 $X\to Y$ と $\mathcal C_T$ の射 $X\rightsquigarrow Y$ は別物なので、合成の記号も $\circ$ と $\circ_T$ で書き分ける。
$\mathcal C_T$ の合成は結合的で、$\eta_X$ は左右の単位元である。すなわち $f\colon X\rightsquigarrow Y$、$g\colon Y\rightsquigarrow Z$、$h\colon Z\rightsquigarrow W$ について
$$
h\circ_T(g\circ_T f)=(h\circ_T g)\circ_T f,\qquad
f\circ_T\eta_X=f=\eta_Y\circ_T f .
$$
要点：単位律は $\eta$ の自然性とモナドの単位律、結合律は $\mu$ の自然性 $T(h)\circ\mu_Z=\mu_{TW}\circ TT(h)$ とモナドの結合律から従う。
計算を開く
単位律：$f\circ_T\eta_X=\mu_Y\circ T(f)\circ\eta_X=\mu_Y\circ\eta_{TY}\circ f=f$、$\eta_Y\circ_T f=\mu_Y\circ T(\eta_Y)\circ f=f$。結合律：$h\circ_T(g\circ_T f)=\mu_W\circ T(h)\circ\mu_Z\circ T(g)\circ f=\mu_W\circ\mu_{TW}\circ TT(h)\circ T(g)\circ f=\mu_W\circ T(\mu_W)\circ TT(h)\circ T(g)\circ f=\mu_W\circ T\bigl(\mu_W\circ T(h)\circ g\bigr)\circ f=(h\circ_T g)\circ_T f$。$\blacksquare$
これは Rie16 Exercise 5.2.iv（p. 197）で確かめるよう求められている事実で、Mac98 Chapter VI §5（pp. 147–148）は証明の概略を述べている。
延長による書き方
$f\colon X\to TY$ に対し $f^\sharp:=\mu_Y\circ T(f)\colon TX\to TY$ とおき、$f$ の 延長 と呼ぶ。Kleisli 圏の合成は $g\circ_T f=g^\sharp\circ f$ と書ける。延長は「$X$ の元ごとに決めた $f$ を、$TX$ の元全体へ広げる」操作で、例では次の形をとる。
- 延長は $\eta_X^\sharp=\operatorname{id}_{TX}$、$f^\sharp\circ\eta_X=f$、$(g^\sharp\circ f)^\sharp=g^\sharp\circ f^\sharp$ を満たす（$f\colon X\to TY$、$g\colon Y\to TZ$）。
- 逆に、$\mathcal C$ の各対象 $X$ に対象 $TX$ と射 $\eta_X\colon X\to TX$ を、各射 $f\colon X\to TY$ に射 $f^\sharp\colon TX\to TY$ を対応させる対応が 1 の三法則を満たすとする。$f\colon X\to Y$ に対し $T(f):=(\eta_Y\circ f)^\sharp$、$\mu_X:=(\operatorname{id}_{TX})^\sharp$ とおくと $(T,\eta,\mu)$ はモナドであり、その延長 $\mu_Y\circ T(f)$ はもとの $f^\sharp$ に一致する。1 と 2 の対応は互いに逆である。
要点：1 はモナドの公理の言い換え、2 は三法則だけで関手性・自然性・モナドの公理を順に計算する。
計算を開く
1：$\eta_X^\sharp=\mu_X\circ T(\eta_X)=\operatorname{id}$ は単位律、$f^\sharp\circ\eta_X=f\circ_T\eta_X=f$ は prop-kl-category である。第三式は、$\mu$ の自然性 $T(g)\circ\mu_Y=\mu_{TZ}\circ TT(g)$ と結合律から $(g^\sharp\circ f)^\sharp=\mu_Z\circ T(\mu_Z)\circ TT(g)\circ T(f)=\mu_Z\circ\mu_{TZ}\circ TT(g)\circ T(f)=\mu_Z\circ T(g)\circ\mu_Y\circ T(f)=g^\sharp\circ f^\sharp$。
2：三法則を順に (K1)・(K2)・(K3) と呼ぶ。関手性：$T(\operatorname{id}_X)=\eta_X^\sharp=\operatorname{id}$ は (K1)。$f\colon X\to Y$、$g\colon Y\to Z$ について、(K3) と (K2) から $T(g)\circ T(f)=(\eta_Z g)^\sharp(\eta_Y f)^\sharp=((\eta_Zg)^\sharp\eta_Yf)^\sharp=(\eta_Zgf)^\sharp=T(gf)$。$\eta$ の自然性：$T(f)\eta_X=(\eta_Yf)^\sharp\eta_X=\eta_Yf$ は (K2)。$\mu$ の自然性：両辺とも $(T(f))^\sharp$ に等しい。実際 $\mu_Y\circ TT(f)=\operatorname{id}^\sharp(\eta_{TY}T(f))^\sharp=(\operatorname{id}^\sharp\eta_{TY}T(f))^\sharp=(T(f))^\sharp$（(K3) と (K2)）、$T(f)\circ\mu_X=(\eta_Yf)^\sharp\operatorname{id}^\sharp=((\eta_Yf)^\sharp)^\sharp=(T(f))^\sharp$（(K3)）。単位律：$\mu_X\eta_{TX}=\operatorname{id}^\sharp\eta_{TX}=\operatorname{id}$ は (K2)、$\mu_XT(\eta_X)=\operatorname{id}^\sharp(\eta_{TX}\eta_X)^\sharp=(\operatorname{id}^\sharp\eta_{TX}\eta_X)^\sharp=\eta_X^\sharp=\operatorname{id}$（(K3)・(K2)・(K1)）。結合律：$\mu_XT(\mu_X)=\operatorname{id}^\sharp(\eta_{TX}\mu_X)^\sharp=(\operatorname{id}^\sharp\eta_{TX}\mu_X)^\sharp=\mu_X^\sharp$、$\mu_X\mu_{TX}=\operatorname{id}^\sharp\operatorname{id}_{TTX}^\sharp=(\operatorname{id}^\sharp)^\sharp=\mu_X^\sharp$。延長の一致：$\mu_YT(f)=\operatorname{id}^\sharp(\eta_{TY}f)^\sharp=(\operatorname{id}^\sharp\eta_{TY}f)^\sharp=f^\sharp$。逆向き：モナドから作った延長で $T,\mu$ を作り直すと $(\eta_Yf)^\sharp=\mu_YT(\eta_Y)T(f)=T(f)$、$\operatorname{id}^\sharp=\mu_X$ で、もとのモナドに戻る。$\blacksquare$
2 の形で与えたモナドを Kleisli 三つ組 ともいう。対象への作用・単位・延長の三つでモナドが決まり、Kleisli 圏は「恒等射が $\eta$、合成が $g^\sharp\circ f$」と直接書ける。
直感
$\mathcal C_T$ の射 $X\rightsquigarrow Y$ は、「$T$ で表される付加情報をともなう、$X$ から $Y$ への写像」である。合成 $g\circ_T f$ では、$f$ の値 $TY$ の中身の各元に $g$ を当てて $TTZ$ の値を得て、$\mu_Z$ で二重の付加情報を一重にまとめる。部分写像では「途中で失敗したら全体も失敗」、関係では「途中で枝分かれした値をすべて集める」という規則が $\mu$ である。
代数の側から見ると、$TY$ は $Y$ で生成される自由代数の台であり、射 $X\to TY$ は自由代数の間の準同型 $TX\to TY$ を生成元で指定したものである。Kleisli 圏は、自由代数とその間の準同型だけを、生成元の集合という小さなデータで記録した圏である（cor-kl-free-algebras）。
Kleisli 圏が定める随伴
関手 $F_T\colon\mathcal C\to\mathcal C_T$ と $U_T\colon\mathcal C_T\to\mathcal C$ を
$$
F_TX=X,\quad F_T(k)=\eta_Y\circ k\quad(k\colon X\to Y),\qquad
U_TY=TY,\quad U_T(f)=f^\sharp=\mu_Y\circ T(f)\quad(f\colon X\rightsquigarrow Y)
$$
で定めると $F_T\dashv U_T$ である。随伴の全単射は $\mathcal C_T(F_TX,Y)=\mathcal C(X,TY)=\mathcal C(X,U_TY)$ の恒等写像、単位は $\eta$、余単位は $\varepsilon_Y=\operatorname{id}_{TY}\colon TY\rightsquigarrow Y$ であり、この随伴が定めるモナドはもとの $(T,\eta,\mu)$ に一致する。
$F_T$・$U_T$ の関手性は、$\eta$ の自然性と prop-kl-extension の 1 から従う。
計算を開く
$F_T(\operatorname{id}_X)=\eta_X$ は恒等射で、$k\colon X\to Y$、$k'\colon Y\to Z$ について $F_T(k')\circ_TF_T(k)=\mu_Z\circ T(\eta_Zk')\circ\eta_Y\circ k=\mu_Z\circ\eta_{TZ}\circ\eta_Z\circ k'\circ k=F_T(k'\circ k)$（$\eta$ の自然性と単位律）。$U_T(\eta_X)=\eta_X^\sharp=\operatorname{id}$、$U_T(g\circ_Tf)=(g^\sharp f)^\sharp=g^\sharp f^\sharp$。
全単射 $\Phi\colon\mathcal C_T(F_TX,Y)\to\mathcal C(X,U_TY)$ を恒等写像とする。自然性は、$k\colon X'\to X$、$g\colon Y\rightsquigarrow Y'$、$f\colon X\rightsquigarrow Y$ について $g\circ_Tf\circ_TF_T(k)=g^\sharp\circ f^\sharp\circ\eta_X\circ k=g^\sharp\circ f\circ k=U_T(g)\circ f\circ k$ となることである（prop-kl-extension の 1 の第二式）。単位は $\Phi(\operatorname{id}_{F_TX})=\eta_X$、余単位は $\Phi^{-1}(\operatorname{id}_{TY})$、すなわち $\mathcal C$ の射 $\operatorname{id}_{TY}$ を $\mathcal C_T$ の射 $TY\rightsquigarrow Y$ と見たものである（随伴関手 の命題「随伴から単位・余単位を取り出す」）。定まるモナドの関手は、対象で $U_TF_TX=TX$、射で $U_TF_T(k)=\mu_Y\circ T(\eta_Y)\circ T(k)=T(k)$ なので $T$ である。乗法は $U_T(\varepsilon_{F_TX})=(\operatorname{id}_{TX})^\sharp=\mu_X\circ T(\operatorname{id}_{TX})=\mu_X$ である。$\blacksquare$
これは Rie16 Lemma 5.2.12（pp. 194–195）、Mac98 Chapter VI §5, Theorem 1（p. 147）である。$F_T$ は対象の上で恒等写像である。Kleisli 圏の対象はどれも「$F_T$ で送った自由な対象」であり、これが次の最小性の源になる。
始対象性
モナド $(T,\eta,\mu)$ を定める随伴とは、関手 $F\colon\mathcal C\to\mathcal D$、$G\colon\mathcal D\to\mathcal C$ の随伴 $F\dashv G$ で、$GF=T$、単位が $\eta$、$G\varepsilon F=\mu$（$\varepsilon$ は余単位）となるものをいう。Kleisli 圏の随伴 $F_T\dashv U_T$ と、Eilenberg–Moore 圏の随伴 $F^T\dashv U^T$（モナドとBarr–Beckの定理 の命題「自由代数と忘却の随伴」）がその例である。
$F\dashv G$ を、$F\colon\mathcal C\to\mathcal D$、余単位 $\varepsilon$ で、モナド $(T,\eta,\mu)$ を定める随伴とする。
- 関手 $L\colon\mathcal C_T\to\mathcal D$ で $L\circ F_T=F$ かつ $G\circ L=U_T$ を満たすものがただ一つ存在する。それは $LX=FX$、$f\colon X\rightsquigarrow Y$（すなわち $f\colon X\to GFY$）に対して $L(f)=\varepsilon_{FY}\circ F(f)$ で与えられる。
- $L$ は充満忠実関手であり、$L$ の像の対象はちょうど $FX$（$X\in\mathcal C$）の形の対象である。
存在：$L(f)=\varepsilon_{FY}\circ F(f)$ は、随伴の全単射による $f\colon X\to GFY$ の転置 $\Phi^{-1}(f)\colon FX\to FY$ である（随伴関手 の命題「随伴から単位・余単位を取り出す」）。恒等射は、三角恒等式から $L(\eta_X)=\varepsilon_{FX}\circ F(\eta_X)=\operatorname{id}_{FX}$ に移る。合成の保存は、$g\circ_Tf=G(\varepsilon_{FZ})\circ GF(g)\circ f$ に $\varepsilon$ の自然性を二度使う。
計算を開く
$f\colon X\to GFY$、$g\colon Y\to GFZ$ とする。$\varepsilon$ の自然性を射 $\varepsilon_{FZ}$ と $F(g)\colon FY\to FGFZ$ に使うと $\varepsilon_{FZ}\circ FG(\varepsilon_{FZ})=\varepsilon_{FZ}\circ\varepsilon_{FGFZ}$、$\varepsilon_{FGFZ}\circ FGF(g)=F(g)\circ\varepsilon_{FY}$ なので、$L(g\circ_Tf)=\varepsilon_{FZ}\circ FG(\varepsilon_{FZ})\circ FGF(g)\circ F(f)=\varepsilon_{FZ}\circ\varepsilon_{FGFZ}\circ FGF(g)\circ F(f)=\varepsilon_{FZ}\circ F(g)\circ\varepsilon_{FY}\circ F(f)=L(g)\circ L(f)$。
$k\colon X\to Y$ について $L(F_T(k))=\varepsilon_{FY}\circ F(\eta_Y)\circ F(k)=F(k)$（三角恒等式）、$f\colon X\rightsquigarrow Y$ について $G(L(f))=G(\varepsilon_{FY})\circ GF(f)=\mu_Y\circ T(f)=U_T(f)$ である。
一意性：$L'$ が二条件を満たすとする。対象については $L'X=L'(F_TX)=FX$ である。$f\colon X\rightsquigarrow Y$ について $L'(f)\colon FX\to FY$ は、どんな射 $e\colon FX\to B$ とも同じく $e=\varepsilon_B\circ F(G(e)\circ\eta_X)$ を満たす（$e$ の転置 $G(e)\circ\eta_X$ をもう一度転置したもの）。$G(L'(f))=U_T(f)=\mu_Y\circ T(f)$ と単位律・$\eta$ の自然性から $G(L'(f))\circ\eta_X=\mu_Y\circ\eta_{TY}\circ f=f$ なので、$L'(f)=\varepsilon_{FY}\circ F(f)=L(f)$ である。
2：$L$ の $\mathcal C_T(X,Y)=\mathcal C(X,GFY)\to\mathcal D(FX,FY)$ への作用は随伴の全単射 $\Phi^{-1}$ そのものなので、$L$ は充満忠実である。像の対象については $LX=FX$ から明らかである。$\blacksquare$
1 は Rie16 Proposition 5.2.13（pp. 195–196）の前半、Mac98 Chapter VI §5, Theorem 2（p. 148）である。モナド $T$ を定める随伴を対象とし、左右の随伴と可換な関手を射とする圏を考えると、1 は Kleisli の随伴がその圏の始対象であることを言っている（Mac98 Chapter VI §5, Theorem 3、p. 148）。Eilenberg–Moore の随伴は同じ圏の終対象である（Eilenberg–Moore圏 の定理「比較関手の一意性」）。
2 から、$\mathcal C_T$ は「$\mathcal D$ の対象 $FX$ とその間の射」の圏を $\mathcal C$ の対象で添字づけたものと見なせる。$F$ が対象の上で単射なら、$L$ は $\mathcal C_T$ から $\{FX\}$ の張る充満部分圏への圏の同型である。
関手 $J\colon\mathcal C_T\to\mathcal C^T$ を、$JX=(TX,\mu_X)$、$f\colon X\rightsquigarrow Y$ に対して $J(f)=f^\sharp=\mu_Y\circ T(f)$ で定める。$J$ は充満忠実であり、像の対象はちょうど自由代数 $(TX,\mu_X)$ である。$J$ は $J\circ F_T=F^T$、$U^T\circ J=U_T$ を満たすただ一つの関手である。
thm-kl-initial を随伴 $F^T\dashv U^T$ に当てる。その余単位は $(A,a)$ で $a$ なので、$\varepsilon_{F^TY}=\mu_Y$ であり、$L(f)=\mu_Y\circ F^T(f)=\mu_Y\circ T(f)$ となって $J$ に一致する。$\blacksquare$
これは Rie16 Lemma 5.2.14（p. 196）である。$J$ が対象の上で $X\mapsto(TX,\mu_X)$ という形をしているので、すべての $T$-代数が自由代数と同型であるときに限って $J$ は本質的全射になる。$J$ が圏同値にならない例は Eilenberg–Moore圏 の反例の表にある。
余積
$\mathcal C$ で対象の族 $(X_i)_{i\in I}$ が余積 $(\coprod_iX_i,(\iota_i)_i)$ をもつなら、$(\coprod_iX_i,(F_T(\iota_i))_i)$ は $\mathcal C_T$ での余積である。
$f\circ_TF_T(\iota_i)=f^\sharp\circ\eta\circ\iota_i=f\circ\iota_i$ なので、射の族 $f_i\colon X_i\rightsquigarrow Y$ を経由させる条件は $\mathcal C$ の射 $f_i\colon X_i\to TY$ についての余積の条件と同じである。$\blacksquare$
例
以下の例はどれも集合の圏 $\mathbf{Set}$ 上のモナドである。
$TX=X\sqcup\{*\}$（$*$ は付け加えた一点）、$\eta_X$ を包含、$\mu_X$ を $X\sqcup\{*\}$ の上では恒等写像で、もう一度付け加えた点を $*$ に送る写像とする（モナドとBarr–Beckの定理 の例「一点を付け加えるモナド」）。$T(g)$ は $Y$ の上で $g$、$*$ を $*$ に送る写像である。
Kleisli 圏の射 $X\rightsquigarrow Y$ は写像 $X\to Y\sqcup\{*\}$ であり、部分写像 の定理「部分写像の全域化」の 1 により部分写像 $X\rightharpoonup Y$ と一対一に対応する（値が $*$ の点で定義されていないとみる）。合成を見る。$\tilde f\colon X\to Y\sqcup\{*\}$、$\tilde g\colon Y\to Z\sqcup\{*\}$ について、$\mu_Z\circ T(\tilde g)\circ\tilde f$ は、$\tilde f(x)=*$ の点を $*$ に、$\tilde f(x)=y\in Y$ の点を $\tilde g(y)$ に送る。これは部分写像の合成 $g\circ f$ を全域化したものである。恒等射 $\eta_X$ は恒等写像を全域化したものである。よって $\mathcal C_T$ は、集合と部分写像の圏 $\mathbf{Par}$ と、対象の上で恒等写像になる関手で同型である（Rie16 Example 5.2.11 (i), p. 194）。
$TX=\mathcal P(X)$（冪集合）、$T(f)$ を順像 $S\mapsto f(S)$、$\eta_X(x)=\{x\}$、$\mu_X$ を和集合をとる写像 $\mathcal S\mapsto\bigcup\mathcal S$ とするとモナドになる（Rie16 Example 5.1.5 (i), p. 187）。
写像 $f\colon X\to\mathcal P(Y)$ に部分集合 $R_f=\{(x,y)\mid y\in f(x)\}\subset X\times Y$ を対応させると、Kleisli 圏の射 $X\rightsquigarrow Y$ は $X$ から $Y$ への二項関係と一対一に対応する。合成は
$$
(g\circ_Tf)(x)=\bigcup\{\,g(y)\mid y\in f(x)\,\}
$$
なので、$(x,z)\in R_{g\circ_Tf}$ は「ある $y$ で $(x,y)\in R_f$ かつ $(y,z)\in R_g$」と同値であり、$R_{g\circ_Tf}=R_g\circ R_f$ は関係の合成である（二項関係 の命題「逆関係と合成」）。恒等射 $\eta_X$ には対角集合 $\Delta_X$ が対応する。よって $\mathcal C_T$ は、集合と二項関係の圏 $\mathbf{Rel}$ と同型である。
prop-kl-coproduct により、$\mathbf{Rel}$ では非交和 $X\sqcup Y$ が余積である。さらに、関係を逆関係に送る対応は $\mathbf{Rel}$ からその反対圏への同型で、対象の上で恒等写像なので（二項関係 の命題「逆関係と合成」の 3）、$X\sqcup Y$ は $\mathbf{Rel}$ の積でもある。$\mathbf{Set}$ では積は直積で余積とは違うので、$\mathcal C_T$ の積は $\mathcal C$ の積から得られるとは限らない。
$R$ を環とし、$TX=R^{(X)}$ を $X$ を基底とする自由左 $R$ 加群の台集合とする（自由加群 の定義「自由加群」の記号で、標準基底の元 $e_x$ を $[x]$ と書く）。$T(f)\bigl(\sum r_x[x]\bigr)=\sum r_x[f(x)]$、$\eta_X(x)=[x]$、$\mu_X\bigl(\sum_ir_i[v_i]\bigr)=\sum_ir_iv_i$（$v_i\in R^{(X)}$ の形式的な一次結合を実際に計算する）とすると、自由加群と忘却の随伴が定めるモナドになる。
Kleisli 圏の射 $f\colon X\rightsquigarrow Y$ は、$X$ の各元に $R^{(Y)}$ の元を割り当てる写像であり、その延長 $f^\sharp=\mu_Y\circ T(f)$ は $[x]\mapsto f(x)$ で定まる $R$ 線形写像 $R^{(X)}\to R^{(Y)}$ である。$R$ 線形写像 $R^{(X)}\to R^{(Y)}$ は基底 $[x]$ での値で一つに決まり（自由加群 の命題「基底上の指定の延長」）、$f^\sharp([x])=f(x)$ なので、$f\mapsto f^\sharp$ は全単射 $\mathcal C_T(X,Y)\to\operatorname{Hom}_R(R^{(X)},R^{(Y)})$ で、合成と両立する。すなわち $\mathcal C_T$ は「基底を指定した自由加群と線形写像」の圏である。$R$ が可換で $X,Y$ が有限集合なら、$f$ は $f(x)$ の係数を第 $x$ 列に並べた $|Y|\times|X|$ 行列で表され、$\circ_T$ は行列の積になる。
体 $k$ 上の群環 $R=k[G]$ なら、$\mathcal C_T$ は正則表現の直和 $k[G]^{(X)}$ と $G$ 同変な線形写像の圏である。$R$ が体のとき、すべてのベクトル空間は基底をもつので（選択公理を使う）、$\mathcal C_T$ は Eilenberg–Moore 圏と同値になる（Rie16 pp. 196–197 の Lemma 5.2.14 の後の説明）。
$M$ をモノイドとし、$TX=X\times M$、$T(f)=f\times\operatorname{id}_M$、$\eta_X(x)=(x,e)$（$e$ は単位元）、$\mu_X((x,m),n)=(x,mn)$ とおくとモナドになる（モナドの公理が $M$ の結合法則と単位元の性質にちょうど当たることを、反例の表の節で確かめる）。射 $f\colon X\rightsquigarrow Y$ は、値 $f_1(x)\in Y$ と「付加量」$f_2(x)\in M$ の組を返す写像で、合成は
$$
(g\circ_Tf)(x)=\bigl(g_1(f_1(x)),\ g_2(f_1(x))\,f_2(x)\bigr)
$$
となる。$M=(\mathbb N,+,0)$ なら、各段の手間を足し合わせる計算になる。
$TX$ を $X$ の元の有限列の集合、$\mu_X$ を列の列をつなげる写像とする（モナドとBarr–Beckの定理 の例「語のモナドとモノイド」）。射 $f\colon X\rightsquigarrow Y$ は各 $x$ に $Y$ の元の列を返す写像で、$(g\circ_Tf)(x)$ は $f(x)=(y_1,\dots,y_n)$ の各項に $g$ を当てた列 $g(y_1),\dots,g(y_n)$ をつなげたものである（Rie16 Example 5.2.11 (ii), p. 194）。cor-kl-free-algebras により、$\mathcal C_T$ は自由モノイドとその間のモノイド準同型の圏と見なせる。
反例の表
Kleisli 圏が圏になる（prop-kl-category）には、モナドの三つの等式がそれぞれ必要である。ex-kl-writer の構成を、$M$ を単位元とは限らない元 $e$ と二項演算をもつ集合に替えて行う。$T=-\times M$ は関手で、$\eta,\mu$ は自然変換になる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 結合律 $\mu_X\circ T(\mu_X)=\mu_X\circ\mu_{TX}$ | $M=\{e,a,b\}$、$e$ は両側の単位元、$aa=ab=b$、$ba=bb=a$ | $\circ_T$ の結合律 |
| 単位律 $\mu_X\circ T(\eta_X)=\operatorname{id}_{TX}$ | $M=\{e,a\}$、積は $mn=m$ | $\eta_Y\circ_Tf=f$ |
| 単位律 $\mu_X\circ\eta_{TX}=\operatorname{id}_{TX}$ | $M=\{e,a\}$、積は $mn=n$ | $f\circ_T\eta_X=f$ |
$TTTX$ の元 $(((x,m),n),p)$ を $\mu_X\circ T(\mu_X)$ は $(x,(mn)p)$ に、$\mu_X\circ\mu_{TX}$ は $(x,m(np))$ に送る。$TX$ の元 $(x,m)$ を $\mu_X\circ\eta_{TX}$ は $(x,me)$ に、$\mu_X\circ T(\eta_X)$ は $(x,em)$ に送る。よって（$X$ が空でないとき）、結合律は $M$ の積の結合法則と、$\mu_X\circ T(\eta_X)=\operatorname{id}$ は $em=m$（すべての $m$）と、$\mu_X\circ\eta_{TX}=\operatorname{id}$ は $me=m$（すべての $m$）と同値である。
各行では、外した等式以外の二つは成り立つ。一点集合上の $f=g=h\colon\mathrm{pt}\mapsto(\mathrm{pt},a)$ で、表の右の列の等式が崩れる。
各行の確かめ
1 行目：$e$ は両側の単位元なので単位律は成り立つ。$(aa)a=ba=a$、$a(aa)=ab=b$ なので結合律は成り立たない。合成の式から $h\circ_T(g\circ_Tf)$ の付加量は $a(aa)=b$、$(h\circ_Tg)\circ_Tf$ の付加量は $(aa)a=a$ で、両者は異なる。
2 行目：$mn=m$ は結合的で（$(mn)p=m=m(np)$）、$me=m$ なので $\mu_X\circ\eta_{TX}=\operatorname{id}$ は成り立つが、$ea=e$ なので $\mu_X\circ T(\eta_X)\ne\operatorname{id}$ である。$\eta\circ_Tf=\mu\circ T(\eta)\circ f$ は $\mathrm{pt}\mapsto(\mathrm{pt},ea)=(\mathrm{pt},e)$ となり、$f$ と異なる。
3 行目：$mn=n$ は結合的で、$em=m$ なので $\mu_X\circ T(\eta_X)=\operatorname{id}$ は成り立つが、$ae=e$ なので $\mu_X\circ\eta_{TX}\ne\operatorname{id}$ である。$f\circ_T\eta=\mu\circ T(f)\circ\eta$ は $\mathrm{pt}\mapsto(\mathrm{pt},ae)=(\mathrm{pt},e)$ となり、$f$ と異なる。
補足
関数型プログラミングでは、失敗・非決定性・状態の更新などの「副作用」をもつ計算を射 $X\to TY$ として扱い、Kleisli 圏の合成でつなぐ。状態の集合 $S$ について $TX=(X\times S)^S$ とおくと、射 $X\rightsquigarrow Y$ は入力と現在の状態から出力と新しい状態を返す写像 $X\times S\to Y\times S$ と同じものになる（Rie16 Example 5.2.11 (iii), p. 194）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
