Haskell 学习笔记 | 范畴论与 Haskell(基础篇)

最近入了 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的对象和态射映射到自身。自函子反映了范畴内部的自相似性。

Functor

在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(用交换图表示):

Natural Transformation

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$)

用交换图表示如下:

Monad coherence condition

注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

参考资料

文章目录
  1. 1. Category
  2. 2. Functor
  3. 3. Bifunctor
  4. 4. Hom-functor
  5. 5. Representable functor
  6. 6. Adjoint functor
  7. 7. Natural Transformation
  8. 8. Monad
  9. 9. TODO
  10. 10. 参考资料