我明明在努力工作，却隔三岔五都会遇到歧视这份职业的人。他们的眼神里，有着对反驳的胆怯与警戒，有时候，还藏着一种 “你敢反驳我便应战” 的好战光芒。

原本以为熟练在 Haskell 中用 Monad 和 Monad transformer 了，结果发现阅读文献碰到时还是绕不开数学。

# Monad 的前世今生

学习 Monad 的时候，如果我们想从数学角度理解，很容易就发现了这样的学习路程：

$$\text{Haskell IO Monad->category theory->Kleisli category->Kleisli triple->algebraic theory}$$

所以我们直接从 algebraic theory 开始，从最抽象的一步步具化到 Monad。

我们基于集合论先进行讨论，然后再用范畴论的语言重述。

# 集合论语言

首先，我们定义一个极其抽象的，称之为 “operator domain” 的东西（用$\Omega$ 表示）。它是一个集合序列$\Omega\triangleq(\Omega_1,\Omega_2,\Omega_3,...)$。

它可以说是毫无信息量了，只表达一个信息：对于$\omega\in\Omega_n$，我们将$\omega$ 看作一个由$n$ 指向 1 的箭头。

Example：

譬如$\Omega=(\{e\},\{i\},\{m\},\emptyset,\emptyset,...)$，可以用下图表示：

然后我们引入$\Omega$-algebra 的概念。一个$\Omega$-algebra 是一个 pair $(X,\delta)$，其中$X$ 是一个集合，而$\delta$ 是一系列函数，对于$\omega\in\Omega_n$，有函数$\delta_\omega:X^n\rightarrow X$。

Example：

延续上面的$\Omega$ 定义，我们可以考虑这样一个$\Omega$-algebra:

$$\begin{aligned} & X=\{0,1\}\\ & \delta_e:\bot\mapsto 1\\ & \delta_i:0\mapsto 0,1\mapsto 1\\ & \delta_m:(0,0)\mapsto 0,(0,1)\mapsto 1,(1,0)\mapsto 1,(1,1)\mapsto 0 \end{aligned}$$

可以看出来，$(X,\delta)$ 其实把$\Omega$ 中的$e$ "翻译" 成了单位元，$i$ 翻译成了逆元，$m$ 翻译成了模 2 加法。

对一个集合$A$，实际上我们可以定义$A\Omega$ 是一个集合，里面的元素被称为 "terms"，是由$A+\Omega$ 中的 symbol 组成的 “合法字符串”。

这个说法很抽象，不妨看一个例子

Example:

延续上面$\Omega$ 定义，我们可以考虑$A=\{x,y,z\}$ 时，那么下面的字符串都是$A\Omega$ terms:

$$x,xym,e,xi,xymzm,xyim\in A\Omega$$

实际上，“合法” 体现在可以被当作后缀表达式 parse 掉。譬如$xym$ 因为$m\in\Omega_2$，可以把它看作一个二元运算符，前面就需要加两个合法的$A\Omega$ 中的 terms。而$xi$ 因为$i\in\Omega_1$ 所以前面只需要加一个 term 就好。

可以注意到，严格来说我们是$A+\Omega$，但实际中我们几乎默认$A$ 和$\Omega$ 没有公共元素（$A$ 看作 elements，$\Omega$ 看作 operations）所以往往直接写$x,y,m$ 而不是$(x,0),(y,0),(m,1)$。

我们继续可以引入$\Omega$-equations 的概念。它也是一个集合，而集合中的元素全部是二元集合。

我们给定一个毫无意义，但是方便 enumerate 的集合$V=\{v_1,v_2,v_3,...\}$ 表示抽象的 variable，那么看一个例子：

Example:

延续上面$\Omega$ 的定义，我们可以定义$\Omega$-equations:

$$E=\{\{v_1v_2mv_3m,v_1v_2v_3mm\},\{v_1v_1im,e\},\{v_1iv_1m,e\}\}$$

虽然看起来很奇怪，但是仔细理解，可以发现它表达了$(v_1+v_2)+v_3=v_1+(v_2+v_3)$，还有$v_1+(-v_1)=0$ 这种含义。

然而这个$E$ 之所以使用的是二元集合而不是等号，是因为$V\Omega$ 中的 terms 是无法判等的！只能等它被某个$\Omega$-algebra 解释后，才可以去判等。

定义好$\Omega$ 和$E$ 后（对于某个$V$），那么$(\Omega,E)$ 就被称为一个 equational presentation。

因为实际上，它只定义了一些 operations 的 domain，还有一些 equational relation。剩下我们一无所知。这个 operation 是什么？加法？这个 equational 是什么？同构？相等？$v_1,v_2$ 是什么？整数？我们都不知道！这就是抽象。

然而有了$\Omega$-algebra，这就都不一样了！我们知道了元素是$X$ 中的，我们知道了应该怎样运算（利用$\delta$）。

Example:

给定$\Omega$-algebra $(X,\delta)$ 后，很显然我们得到了一被称为 total description map 的东西：$\delta^*:X\Omega\rightarrow X$，递归定义为：

$$x\delta^* =x\\ p_1p_2...p_n\omega\delta^* =p_1\delta^*p_2\delta^* ...p_n\delta^* \delta_\omega$$

仔细看看就知道它这是在利用$\delta$ 在进行计算！计算结果就还是$X$ 中的元素。

那么，给定一个$r:V\rightarrow X$ 把抽象的 variable 映射到具体的$X$ 中的元素，很显然我们可以诱导出$r^\dagger :V\Omega\rightarrow X\Omega\rightarrow X$。即我们先把$V\Omega$ 中 terms 里的 abstract variable 换成$X$ 中的元素，再利用$\delta^*$ 进行计算。

此时我们可以引出$(\Omega,E)$-algebra 的定义了！（注意，之前的 algebra 是没有$E$ 的）

注意，这里说了对于任意 assignment，实际上也就是$x+(-x)=0$ for all $x$ 的意思。而这里的 for all 体现在把 abstract variable 映射到具体元素函数$r$ 的任意上。

能用$\Omega,E,\delta,X$ 这样定义出的$(\Omega,E)$-algebra 被称为 equationally definable class of algebra。

于是对于任意 set $A$，如果我们有 function $f:A\rightarrow X$，那就可以自然地 extend 出一个$f^\dagger:A\Omega\rightarrow X$ 的出来。

之前说了，$V\Omega$ 中的 terms 是无法判等的，那么现在给定一个 equational presentation $(\Omega,E)$，和一个任意的集合$A$，我们定义一个$A\Omega$ 上的等价关系：

$$E_A=\{(p,q)\in A\Omega\times A\Omega\mid\text{for all }(\Omega,E)\text{ algebra }(X,\delta)\text{ and functions }f:A\rightarrow X,f^\#p=f^\#q\}$$

Example:

沿用之前的定义：

$$\Omega=(\{e\},\{i\},\{m\},\emptyset,...)\\ E=\{\{xymzm,xyzmm\},\{xxim,e\},\{xixm,e\},\{exm,x\},\{xem,x\}\}$$

那么很显然，对于$A=\{x,y,z\}$ 有：

$$p=xxximm\in A\Omega\\ q=x\in A\Omega$$

而$p=q$。这是一件很自然的事，因为要满足$E$，就自然会导致$p,q$ 在所有$(\Omega,E)$-algebra 下是相等的。

$E_A$ 的定义，就是把原先$A\Omega$ 这个不可比的集合，利用$E$ 而引入了等价关系变得可比！

我们记$AT=A\Omega/E_A$（$T$ is for ‘‘theory’’），并且自然地引入一个映射$A\rho:A\Omega\rightarrow AT$，也就是把$p\in A\Omega\mapsto [p]\in AT$。

Example:

沿用上述的定义，实际上我们有：

$$[xxximm]=[xem]=[x]$$

它们都是一个等价类里的（可以看作是化简）

实际上，$AT$ 就是一个$(\Omega,E)$-algebra！这是怎么定义的呢？

$$X\triangleq AT=A\Omega/E_A\\ [p_1][p_2]...[p_n]\delta_\omega\triangleq[p_1p_2...p_n\omega]\\ \delta_\omega:AT^n\rightarrow AT$$

那么给定一个 equational presentation $(\Omega,E)$，我们可以定义：

Example:

考虑$\Omega=(\{e\},\{i\},\{+\},\emptyset,\emptyset,...)$，以及$E=\emptyset$。那么此时显然$E_A=\emptyset$ 对于任意$A$，所以也有$AT=A\Omega/E_A=A\Omega$。

假如我们有四个集合：

$$\begin{aligned} & A = \{1\}\\ & B=\{b,x\}\\ & C = \{c,y\}\\ & D = \{d,z\} \end{aligned}$$

然后有三个函数：

$$\begin{aligned} & \alpha:A\rightarrow BT=B\Omega\\ &\beta:B\rightarrow CT=C\Omega\\ &\gamma:C\rightarrow DT=D\Omega \end{aligned}$$

函数内容为：

$$\begin{aligned} & \alpha= &&1\mapsto xie+b+\\ & \beta= && x\mapsto y\\ & && b\mapsto cc+\\ &\gamma= && c\mapsto dz+i\\ & && y\mapsto e \end{aligned}$$

那么有：

$$\alpha\circ(\beta\circ\gamma):A\rightarrow DT\\ (\alpha\circ\beta)\circ\gamma:A\rightarrow DT$$

且：

$$\begin{aligned} & (\beta\circ\gamma)= && b\mapsto dz+idz+i+\\ & && x\mapsto e\\ & \alpha\circ(\beta\circ\gamma)= && 1\mapsto eie+dz+idz+i++\\ & (\alpha\circ\beta)= && 1\mapsto yie+cc++\\ & (\alpha\circ\beta)\circ\gamma= && 1\mapsto eie+dz+idz+i++ \end{aligned}$$

所以有$\alpha\circ(\beta\circ\gamma)=(\alpha\circ\beta)\circ\gamma$。

上个例子其实说明了，morphism 就是 substitution 的过程，也其实揭示了证明的内涵：证明某个命题，本质上就是一直在 substitute axiom 中的 variable。

到这里或许读者已经初见端倪，为什么我们应该把 Monad 理解成一种 computation。

因为从只含有 variable 的集合$A$，后面引入了$\Omega$ 中定义的 operations 得到$A\Omega$，然后进一步引入了$E$ 中的相等关系得到了$AT$。

$A\Omega$ 中的 terms 可以看作是表达式了，而$AT$ 中的元素则可以看作有了$E$ 给的化简规则后，化简的结果。

而 terms in $A\Omega$ 就可以看作是证明（Curry-Howard 同构），morphism $A\rightarrow BT$ 就告诉我们，得到了一个$AT$ 中的 terms，如何通过 substitution 得到一个$BT$ 中的 term。

这时候，我们会发现没有 types 怎么办。所以我们需要引入 2-category！！

object 是 types，morphism 是 terms，然后 morphism 之间的 morphism 是 substitution。

---

以下为原始 note：

# 单位半群（Monoid）

” 这个相对简单，就是一个代数结构。当集合$S$ 上存在一个二元运算$*:S\times S\rightarrow S$ 和一个单位元$e\in S$ 满足：

1. $\forall a\in S,\;e*a=a*e=a$.

2. $\forall a,b,c\in S,\; a*(b*c)=(a*b)*c$.

那我们就称集合$S$ 和这个运算、单位元形成了一个单位半群（幺半群，Monoid）

例：自态射形成了一个 Monoid。考虑一个 category $\mathcal{C}$ 中只有一个元素$a$ 和很多 morphism，那么这些 morphism 都是从$a$ 到$a$ 的箭头，他们形成了一个 Monoid。其中$S$ 就是这些 morphism，二元运算是 morphism 的组合，单位元是 identity morphism。由于 category 的性质，故满足结合律和单位律，故形成了一个 Monoid。

# Monoidal Category

关于这个定义，可以说明几点。

1. 这个 monoidal structure 里的元素（譬如单位元），都是 category $\mathcal{C}$ 里面的 object。也就是说我们希望这个 category 本身就有一点 monoid 的结构。但是它不是一个 monoid 在于，结合律和单位律都是同构而不是相等。譬如在 category $\textbf{Set}$ 中，就是集合的同构而不是集合的相等。$\{(a,(b,c))\}$ 和$\{((a,b),c)\}$ 就是同构但不相等的。

2. 其次下面的 coherence conditions 其实是，我们可以利用$\alpha$ 找出很多个诸如下面这种同构：

   $$(((A_1\otimes A_2)\otimes A_3)\otimes ...\otimes A_n)\cong(A_1\otimes (A_1\otimes (A_3\otimes ...\otimes A_n)))$$

   因为你可以选择拆括号时不同的顺序，从而选择$\alpha$ 的不同的 arguments。coherence condition 就说明，这些同构都应该是同一个。

例：把 category $\textbf{Set}$ 补充成一个 monoidal category。bifunctor 选择笛卡尔积，即$A\otimes B=\{(a,b)\mid a\in A,b\in B\}$。然后 unit object 选择为一个特殊的单元素集$\{*\}$。可以验证譬如$\{((1,2),3),((4,5),6)\}\cong \{(1,(2,3)),(4,(5,6))\}$，以及$\{(1,*),(2,*)\}\cong\{1,2\}$ 这样有自然的 isomorphism 满足要求和 coherence condition。

# Monoid in monoidal category

下面我们定义，在一个 monoidal category 上自然导出一个 monoid：

例：考虑$\textbf{Set}$ 是一个 monoidal category，那么我们选择其中一个 object，譬如$M=\{0,1\}$。那么$M\otimes M=\{(0,0),(0,1),(1,0),(1,1)\}$。我们可以找到一个 morphism $\mu$，即模 2 乘法：

$$\mu(0,0)=0\\ \mu(0,1)=0\\ \mu(1,0)=0\\ \mu(1,1)=1$$

对于$\eta$，我们需要找到一个$\{*\}\rightarrow\{0,1\}$ 的映射，很显然有两个选择。如果我们选择$\eta_*=0$ 会怎样？那么第二个 diagram 将不 commute！因为$I\otimes M\stackrel{\eta\otimes 1}{\longrightarrow}M\otimes M\stackrel{\mu}{\longrightarrow}M$ 就会有映射：$(*,1)\mapsto(0,1)\mapsto 0$，显然这和直接用消去映射$\lambda(*,1)=1$ 得到的结果不一样。

所以我们需要选择$\eta_*=1$，这样就满足了要求。这个例子也阐释了，我们是怎么利用已有的 monoidal category 中那些 monoid structure（即$\alpha,\lambda,\rho$）构造一个 monoid 的。

# Monad

最终我们定义一个特殊情况：Monad is a monoid in the (monoidal) category of endofunctors.

考虑一个 category $\mathcal{C}$，显然可以找到一个 category $\mathcal{D}$：

• $\mathcal{D}$ 中的 object 是$\mathcal{C}\rightarrow\mathcal{C}$ 的 functor。
• $\mathcal{D}$ 中的 morphism 是 functor 之间的 natural transformation。

那么$\mathcal{D}$ 是一个 monoidal category：

• 对于两个 functor $F,G\in\mathcal{D}$，$F\otimes G=F\circ G\in\mathcal{D}$。
• $I=1_{\mathcal{C}}$ 即$\mathcal{C}$ 上的 identity functor。

不难验证，这满足 monoidal category 的要求。实际上，$\mathcal{D}$ 是一个 strict monoidal category，因为根据 category 和 functor 的要求，实际上就有$F\circ(G\circ H)=(F\circ G)\circ H$，即不是同构而是直接相等。

那么我们就可以找出$\mathcal{D}$ 中的一个元素和两个 morphism，然后导出一个 monoid，即是 monad：

显然$T$ 是$\mathcal{D}$ 中的一个元素，而$\mu,\eta$ 也对应了导出 monoid 在 endofunctor category 下的情况。而特别的地方在于，由于 endofunctor category 是 strict monoidal category，那么$\alpha,\lambda,\rho$ 都是单位映射，即相等（因为在 category 里，要求了$1_{\mathcal{C}}\circ T=T\circ 1_{\mathcal{C}}=T$）。所以图中省略了$\alpha$ 部分，把$T\circ (T\circ T)$ 和$(T\circ T)\circ T$ 直接合并了，而且在右图中将$\lambda,\rho$ 改写为$=$。

例：我们仍考虑 category $\textbf{Set}$，那么 powerset 实际上就是一个 Monad。考虑一个 endofunctor $T(A\in\textbf{Set})=2^A\in\textbf{Set}$，那么我们可以定义$\eta_A:1_{\textbf{Set}}(A)\rightarrow T(A)$ 为$\eta_A(a\in A)=\{a\}$，譬如对于$A=\{1,2,3\}$，那么$A\stackrel{\eta_A}{\mapsto}\{\{1\},\{2\},\{3\}\}$。

然后定义$\mu_A:T(T(A))\rightarrow T(A)$ 其实就是把集合 flatten 一层。譬如对于$A=\{\{\{1,2\},\{3,4\}\},\{\{5\}\}\}$，那么$A\stackrel{\eta_A}{\mapsto}\{\{1,2,3,4\},\{5\}\}$。这就形成了一个 Monad。

注意，实际上 functor $T$ 应该不仅描述了 object 间的映射关系，还需要说明 morphism 间的映射关系。而$\textbf{Set}$ 上的 morphism 是集合之间的函数，那么对于 powerset 这个$T$，一个很自然的映射就是把函数（譬如$f(x)=x+1$）apply 在 powerset 里的每个 set。