最近入了 Haskell 的坑了。俗话说得好，一入 FP 深似海，从此 Monad 皆是自函子范畴上的幺半群。。。本篇文章主要总结范畴论基础。。。

Category

一个 范畴 $C$ 由以下三部分组成：

• 一些 对象(object)构成的类 $ob(C)$
• 范畴 $C$ 中对象之间的映射，称为 态射(morphism)。对于范畴 $C$ 中任意两个object $A$、$B$，所有的 $A \to B$ 态射的集合用 $hom(A, B)$ 表示，其中 $A$ 称为domain，$B$称为codomain
• 态射的复合运算($\circ$)，用于将多个态射进行复合。比如 $f: \ A \to B$, $g: \ B \to C$，则$g \circ f: \ A \to C$

对范畴中的每一个 object $X$，都存在对应的幺元 $id_{X}: X \to X$ ，并且满足关系：

$$ id(B) \circ f = f = f \circ id(A) $$

同时，复合运算是可结合的，比如 $ (h \circ g) \circ f = h \circ (g \circ f) $。

在 Haskell 中，对应的是：

• object对应着某个具体的函数（类型？）（这是我的理解，也有很多人认为对象对应着某一类值的集合，即类型。我的理解是type和type constructor都可以看作是function）
• 态射对应着函数之间的映射，这种映射产生新的函数。比如 $f :: (a \to b) \to a \to b$
• 态射的复合运算代表着函数的复合（复合函数），比如 h = f . g

Functor

在范畴论中，morphism 是 object 与 object 之间的映射。那么肯定还有 category 与 category 之间的映射，这称为函子（Functor）。

既然是范畴之间的映射，那么函子F的作用就有两个：

• 将范畴C的object($X$)映射到范畴D的object ($F(X)$)
• 将范畴C的morphism($f: \ X \to Y$)映射到范畴D的morphism($F(f) : \ F(x) \to F(Y)$)

并且需要满足两个条件：

• 单位态射关系：$\forall X \in C, F(id_{X}) = id_{F(X)}$
• 分配率：$\forall f:X \to Y, g: Y \to Z \in C, F(g \circ f) = F(g) \circ F(f)$

一般的函子都是协变函子(covariant functor)。将函子中的某个范畴 $C$ 替换为其对偶范畴 $C^{OP}$ 即可得到逆变函子(contravariant functor): $F \ : \ C^{OP} \to D$。

将范畴映射到自身的函子称为自函子(endofunctor)，即把范畴C的对象和态射映射到自身。自函子反映了范畴内部的自相似性。

在Haskell中，Functor是一个 typeclass，它是这样定义的:

1
2

class Functor f where
    fmap :: (a -> b) -> f a -> f b

其中f是一个 type constructor，它接收一个concrete type（实际类型）以构造出一个concrete type，其kind为* -> *。

如果这里的object对应Haskell里的类型的话，那么type constructor相当于morphism，它就是自函子的一部分，即一个范畴的object与另一个范畴的object的映射。

类型与类型的映射一般都是简单类型与复杂类型之间的相互转化，比如int -> Maybe int。而另一部分，即态射与态射之间的映射，其实就是高阶函数（函数与函数之间的映射，因为态射本身就对应Haskell中的函数），在Haskell的Functor里面对应的就是fmap，它将态射a -> b映射为另一个态射f a -> f b:

$$(a \to b) \to f \ a \to f \ b$$

Bifunctor

Bifunctor(二元函子)与普通的Functor区别之处在于Bifunctor的domain为两个范畴的积，比如 $F: \ C_{1} \times C_{2} \to D$。

Hom-functor

对于一个范畴 $C$，其 hom-functor 的定义为：$Hom(-,-) : \ C^{OP} \times C \to Set$，它是一个bifunctor。

从hom-functor中衍生出的两个函子：

• covariant hom-functor: $Hom(A, -): \ C \to Set$，通常称为 copresheaf
• contravariant hom-functor: $Hom(-, A): \ C^{OP} \to Set$，通常称为 presheaf

Representable functor

若函子 $F: \ C \to Set$ 自然同构于 $Hom(A, -)$，其中 $A \in C$，则 $F$ 就是一个Representable functor。

相似地，若函子 $F: \ C^{OP} \to Set$ 自然同构于 $Hom(-, A)$，其中 $A \in C$，则 $F$ 就是一个Corepresentable functor。

注：Forgetful functors to $Set$ are very often representable.

Adjoint functor

若有两个函子 $F: \ D \to C$ 以及 $G : \ C \to D$ 满足以下自然同构关系：

$$Hom_{C}(F(-), -) \cong Hom_{D}(-, G(-))$$

即对于 $\forall X \in C, Y \in D$，满足：

$$Hom_{C}(F(Y), X) \cong Hom_{D}(Y, G(X))$$

那么这两个函子就是一对伴随函子(adjoint functor)，并称F是G的左伴随函子，记为 $F \dashv G$。

• 常见的一对伴随函子：Forgetful Functor/Free Functor。$Forget : \ C \to Set$，$Free : \ Set \to C$，$Free \dashv Forget$。

Natural Transformation

再抽象一层，自然变换(Natural Transformation)是Functor之间的映射关系。

假设 $F$ 和 $G$ 是范畴 $C$ 到范畴 $D$ 的函子 $C \to D$，则 $F$ 到 $G$的自然变换 $\tau : F \to G$ 是一个作用于 $C$ 中任意对象 $X$ 的 D-morphism ：$\tau_{X} : F X \to G X$，且满足以下naturality condition(用交换图表示)：

Monad

这里先总结一下 Monad 的范畴论定义。Monad 由三元组 $<T, \eta, \mu>$ 构成。其中:

• $T$ 为范畴 $X$ 上的自函子： $T: X \to X$
• $\eta$ 为单位自函子 $id_{X}$ 到函子 $T$ 的自然变换：$\eta: id_{X} \to T$
• $\mu$ 为函子 $T$ 的张量积 $T \circ T$ 到函子 $T$ 的自然变换：$\mu: T \circ T \to T$

同时它需要满足以下 coherence condition：

• $\mu \circ T \mu = \mu \circ \mu T$ (即自然变换 $T^{3} \to T$)
• $\mu \circ T \eta = \mu \circ \eta T = 1_{T}$ (即自然变换 $T \to T$)

用交换图表示如下：

注1：此处函子的张量积 $\otimes$ 可以看作为组合(composition)。

注2：注意结合 Monoidal Category 理解；注意里面的Monoid与抽象代数中幺半群的区别。

TODO

• Monoidal Category / Monoidal Functor
• Monad 的来源、推导
• Kleisli 范畴下 Monad 的定义
• Free Monad
• Yoneda Lemma
• Yoneda Embedding/Profunctor
• Day Convolution
• Kan Extensions
• Universal Construction

参考资料

• Jiri Adamek, Horst Herrlich, George Strecker. Abstract and Concrete Categories: The Joy of Cats.
• Saunders Mac Lane. Categories for the Working Mathematician.
• Haskell/Category theory - Wikibooks
• A monad is just a monoid in the category of endofunctors, what’s the issue? - StackOverflow
• hom-functor - nLab
• Typeclassopedia - Haskell Wiki