「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定义是:

1
2
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的定义是:

1
2
3
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}$,而且它可以和>>=互相定义:

1
2
3
4
5
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
    1
    2
    3
    4
    5
    6
      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
    1
    2
    3
    4
      m >>= return 
    = join (fmap return m) = join . fmap return $ m
    = id m
    = m
  3. (m >>= f) >>= g = m >>= (\x -> f x >>= g)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
      (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


目录

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

「Learn Haskell」#A Haskell与范畴论

https://blog.tonycrane.cc/p/96c32eae.html

作者

TonyCrane

发布于

2021-07-19

更新于

2021-07-25

许可协议