「Learn Haskell」#A Haskell与范畴论

Haskell中的函子单子等都与范畴论（category theory）有很多联系，所以打算简单了解一下范畴论的相关内容。

范畴论是数学的一门学科，以抽象的方法处理数学概念，将这些概念形式化成一组组的“物件”及“态射”。数学中许多重要的领域可以形式化为范畴。使用范畴论可以令这些领域中许多难理解、难捉摸的数学结论更容易叙述证明。

———— 维基百科

范畴（Category）

范畴本质上是一个简单的集合，一个范畴$\mathbf{C}$包含三个组成成分：

• 一个类$\mathrm{ob}(\mathbf{C})$：其中元素称为对象（objects）
• 一个类$\mathrm{hom}(\mathbf{C})$：其中元素称为态射（morphisms）（或箭号（arrows））：每个态射连接了两个对象：源对象（source object）、目标对象（target object）。如果$f$是从源对象$A$到目标对象$B$（$A, B\in \mathrm{ob}(\mathbf{C})$）的态射，那么记为$f : A\to B$
• 一个二元运算，称为态射复合（composition）：两个态射$g : A\to B$、$f : B\to C$的复合记为$f\circ g : A\to C$
  在Haskell和大部分数学理论中都是从右向左计算，即$f\circ g$中是先计算$g : A\to B$再计算$f : B\to C$

许多东西都可以组成范畴。比如:

 $\mathbf{Set}$是一个范畴，对象为所有集合，态射为集合之间的函数，复合即函数之间的复合

 $\mathbf{Grp}$是一个范畴，对象为所有群，态射为群同态（group homomorphisms），例如对于群$(G,*)$和$(H,\cdot )$，有群同态$h : (G,*)\to (H,\cdot )$，则需要对于$G$中的任意元素$u,v$满足
$$h(u*v)=h(u)\cdot h(v)$$

注意：态射不必须为函数；而且可以存在源对象和目标对象都相同的不同态射

范畴公理

每个范畴都需要满足三条定律：

1. 态射复合需要满足结合律（associativity）：
   $$f\circ (g\circ h) = (f\circ g)\circ h$$
2. 范畴在复合操作下是闭合的（closed）：
      如果范畴$\mathbf{C}$中存在态射$f : B\to C$、$g : A\to B$，那么范畴$\mathbf{C}$中也一定存在态射$h : A\to C$，且$h=f\circ g$
3. 每个对象都需要有单位态射（identity morphisms）：
      对于范畴$\mathbf{C}$中的对象$A$，一定存在单位态射$\mathrm{id}_A : A\to A$，且对于每个态射$g : A\to B$，一定有：
   $$g\circ\mathrm{id}_A = \mathrm{id}_B\circ g = g$$

$\mathbf{Hask}$范畴

范畴$\mathbf{Hask}$的对象为Haskell中的类型（types），态射是Haskell中的函数，复合运算是(.)。即从类型A到类型B的函数 f :: A -> B 就是$\mathbf{Hask}$范畴中的一个态射。而函数 f :: B -> C 、g :: A -> B 的组合 f . g 就是一个新的函数 h :: A -> C。

对于三条定律：

1. 第一条显然满足：f . (g . h) = (f . g) . h
2. 第二条也显然满足，如果有函数 f :: B -> C 、g :: A -> B，一定有函数 h = (f . g) :: A -> C
3. 对于第三条定律，Haskell中存在单位函数 id ，但id是多态（polymorphic）的，要为其指定类型使其变成单态（monomorphic）的。比如态射$\mathrm{id}_A$在Haskell中就可以表示为 id :: A -> A。并且显然满足第三条定律（其中 f :: A -> B）：

   (id :: B -> B) . f = f . (id :: A -> A) = f

函子（Functors）

一个范畴中的态射将两个对象联系起来，而函子则会将两个范畴联系起来。换句话说，函子就是从一个范畴到另一个范畴的变换。比如对于范畴$\mathbf{C}$、$\mathbf{D}$，定义函子$F : \mathbf{C}\to\mathbf{D}$满足：

• 对于$\mathbf{C}$中的任意对象$A$，在$\mathbf{D}$中都有对象$F(A)$
• 对于$\mathbf{C}$中的任意态射$f : A\to B$，在$\mathbf{D}$中都有态射$F(f) : F(A)\to F(B)$

比如：

 遗忘函子（forgetful functor）$U : \mathbf{Grp}\to\mathbf{Set}$，将一个群映射到一个集合中，将群同态映射到集合间的函数

 幂集函子（power set functor）$P : \mathbf{Set}\to\mathbf{Set}$，将一个集合映射到它的幂集，将原集合中的函数$f : A\to B$映射到函数$P(f) : \mathcal{P}(A)\to\mathcal{P}(B)$，即从$U\subseteq A$到值域$f(U)\subseteq B$的映射

 自函子（endofunctor）$1_{\mathbf{C}} : \mathbf{C}\to\mathbf{C}$，将一个范畴映射到它本身

函子公理

函子$F : \mathbf{C}\to\mathbf{D}$也需要满足两个公理：

1. 对于任意对象$X\in\mathbf{C}$，恒有$F(\mathrm{id}_X)=\mathrm{id}_{F(X)}$
2. 对于态射$f : Y\to Z$、$g : X\to Y$，恒有$F(f\circ g) = F(f)\circ F(g)$

$\mathbf{Hask}$范畴上的函子

Haskell中的Functor定义是：

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

对于Haskell中的Functor，它实际上是从$\mathbf{Hask}$范畴（types）到它子范畴的变换。比如列表函子$\mathtt{[]} : \mathbf{Hask}\to\mathbf{Lst}$（其中$\mathbf{Lst}$是所有Haskell中列表类型构成的范畴）

它也达成了范畴论中对于函子的要求。函子需要进行两个操作：将一个范畴中的对象映射到另一个范畴中、将一个范畴中的态射映射到另一个范畴中。以Maybe为例，它实现了函子的要求：

1. Maybe是一个类型构造器，他可以将任意类型 T 变成新类型 Maybe T，相当于从$\mathbf{Hask}$范畴的对象变成了$\mathbf{Maybe}$范畴的对象
2. fmap函数接收一个 a -> b 类型的函数，返回一个 Maybe a -> Maybe b 类型的函数，相当于将$\mathbf{Hask}$范畴中的态射$f : A\to B$映射成了$\mathbf{Maybe}$范畴中的态射$\mathbf{Maybe}(f) : \mathbf{Maybe}(A)\to\mathbf{Maybe}(B)$

注意：时刻记住这里研究的是$\mathbf{Hask}$范畴和它的子范畴，对象是类型而不是值，态射是函数也指的是从类型到类型

同时，Haskell中的Functor也满足函子公理：

1. fmap id = id 即 fmap (id :: A -> A) = (id :: f A -> f A)
2. fmap (f . g) = fmap f . fmap g

单子（Monads）

一个单子说白了不过就是自函子范畴上的一个幺半群而已 _(:з」∠)_

自函子在前面说到过是从一个范畴到自身的一个函子，如范畴$\mathbf{C}$上的自函子是$F : \mathbf{C}\to\mathbf{C}$。自函子范畴就是对象都是自函子的范畴。幺半群和Haskell中学到的Monoid类型类一样，是一个有可结合二元运算和单位元的代数结构。因此单子就是一个自函子，而且它有可结合二元运算（Haskell中>=>）和单位元（Haskell中return）。

一个单子$M : \mathbf{C}\to\mathbf{C}$还包含两个态射（对于范畴$\mathbf{C}$中的所有对象$X$）：

1. $\mathrm{unit}_X^M : X\to M(X)$
2. $\mathrm{join}_X^M : M(M(X))\to M(X)$

（当式子中的单子明显是$M$时，可以省略上标${}^M$）

Haskell中Monad的定义是：

class Functor m => Monad m where 
    return :: a -> m a 
    (>>=)  :: m a -> (a -> m b) -> m b

其中很显然多态函数return对应了定义中的$\mathrm{unit}$，但是>>=和$mathrm{join}$的对应关系并不明显。因此Haskell中有一个工具函数join，它的效果就是定义中的$\mathrm{join}$，而且它可以和>>=互相定义：

join :: Monad m => m (m a) -> m a
join x = x >>= id

(>>=) :: m a -> (a -> m b) -> m b 
x >>= f = join $ fmap f x

所以Haskell中为Monad要求定义>>=就相当于定义了$\mathrm{join}$

例如，幂集函子$P : \mathbf{Set}\to\mathbf{Set}$也是一个单子，可以为它定义$\mathrm{unit}$和$\mathrm{join}$两个态射。Haskell中的列表也可以近似看作幂集函子。

 态射/函数的类型：

幂集函子	Haskell中列表
一个集合$S$和一个态射$f : A\to B$	一个类型 T 和一个函数 f :: A -> B
$P(f) : \mathcal{P}(A)\to\mathcal{P}(B)$	fmap f :: [A] -> [B]
$\mathrm{unit}_S : S\to\mathcal{P}(S)$	return :: T -> [T]
$\mathrm{join}_S : \mathcal{P}(\mathcal{P}(S))\to\mathcal{P}(S)$	join :: [[T]] -> [T]

 态射/函数的定义：

幂集函子	Haskell中列表
$(\mathcal{P}(f))(S) = \{f(a):a\in S\}$	fmap f xs = [ f a | a <- xs ]
$\mathrm{unit}_S(x) = \{x\}$	return x = [x]
$\mathrm{join}_S(L) = \bigcup L$	join xs = concat xs

单子公理

给定一个单子$M : \mathbf{C}\to\mathbf{C}$，和一个态射$f : A\to B$（其中$A,B\in \mathbf{C}$），那么满足下面四条定律：

1. $\mathrm{join}\circ M(\mathrm{join})=\mathrm{join}\circ\mathrm{join}$
2. $\mathrm{join}\circ M(\mathrm{unit})=\mathrm{join}\circ\mathrm{unit}=\mathrm{id}$
3. $\mathrm{unit}\circ f = M(f)\circ\mathrm{unit}$
4. $\mathrm{join}\circ M(M(f)) = M(f)\circ\mathrm{join}$

也可以很自然地将其转化为Haskell中的表述：

1. join . fmap join = join . join
2. join . fmap return = join . return = id
3. return . f = fmap f . return
4. join . fmap (fmap f) = fmap f . join

在Haskell中，使用>>=也有三个定律和这四个定律是等价的：

1. return x >>= f = f x

     return x >>= f 
   = join (fmap f (return x)) = join (fmap f . return $ x)
   = join (return (f x)) = join (return . f $ x)
   = join . return $ (f x)
   = id (f x)
   = f x

2. m >>= return = m

     m >>= return 
   = join (fmap return m) = join . fmap return $ m 
   = id m
   = m 

3. (m >>= f) >>= g = m >>= (\x -> f x >>= g)

     (m >>= f) >>= g 
   = (join (fmap f m)) >>= g = join (fmap g (join (fmap f m)))
   = join . fmap g . join $ fmap f m 
   = join . join . fmap (fmap g) $ fmap f m 
   = join . join . fmap (fmap g) . fmap f $ m 
   = join . join . fmap (fmap g . f) $ m 
   = join . fmap join . fmap (fmap g . f) $ m 
   = join . fmap (join . (fmap g . f)) $ m 
   = join . fmap (\x -> join (fmap g (f x))) $ m 
   = join . fmap (\x -> f x >>= g) $ m 
   = join (fmap (\x -> f x >>= g) m)
   = m >>= (\x -> f x >>= g)

（范畴论就先简单看这些，只是为了更好理解Haskell中概念而已）

Reference

• Haskell/Category theory - wikibooks
• Category theory - wikipedia
• 范畴论 - 维基百科
• Monad (category theory) - wikipedia
• Functor - wikipedia

---

目录

#0 | 总章        
#1 | 基础语法与函数   
#2 | 高阶函数与模块   
#3 | 类型与类型类    
#4 | 输入输出与文件   
#5 | 函子、应用函子与单子
#6 | 半群与幺半群    
#7 | 一些其它类型类   
#A | Haskell与范畴论