Haskell和范畴论(上)

前言

Haskell 是有名的函数式编程语言. 支持函数式编程的语言很多,但是像 Haskell 这样不使用函数式的思维写不出代码的实属罕见. Haskell本身偏学术性质, 学术界有很多新奇的东西能够在Haskell 找到. 最有名的当属 Monad . 现代的编程语言理论与范畴论联系紧密. Haskell 中有很多衍生自范畴论的语言. 本文主要讨论这些概念.

代数数据类型 (ADT)

代数数据类型(Algebraic Data Type, ADT) 是Haskell中非常有趣而重要的东西. 类型可以看作一个集合,某个类型的值就是这个集合中的元素. Haskell 中的类型有 Sum Type 和 Product Type , Sum Type 使用 | 符号连接,代表类型之间是或的关系, Product Type 一般使用多个元素的构造器连接. 如果将 Type 看作集合, 那么 Sum Type 对应集合范畴中的无交并, Product Type 对应集合范畴中的笛卡尔积.

1
2

data Maybe a = Empty | Full a -- Sum Type
data Vector a b c = Vector a b c -- Product Type

Haskell 中的所有类型构成了一个范畴,其中的对象是 Haskell 中的类型. 态射是这些类型之间的函数. 这个范畴称之为 Hask 范畴 . Product Type 是这个范畴中的 Product, Sum Type 是这个范畴的 Coproduct . Haskell 中的代数数据类型很有意思的一点是,它还支持 Recursive Type ,即在类型的定义中递归. 比如 List 的定义就是一个很有名的例子.

1

data List a = Nil | a : List a -- Recursive Type

Typeclass

Haskell 中第一个和寻常语言不同的概念就是 Functor . 要说明 Functor ,首先得介绍 Typeclass 的概念.

Typeclass 是 Haskell 中用来描述类型特性的关键字. 它用来描述这些类型具有什么样的操作, 这些操作类似其他语言中的 接口 , 但应当注意 Typeclass 属于更高阶的抽象,是用来描述类型的, 这和接口是完全不一样的.

例如 Eq 类型类描述了一类可以判断是否相等的类型. 它必须定义 == 这一函数.

1
2

class Eq a where
  (==) :: a -> a -> Bool

class 关键字说明了一个 Typeclass 应当具有的抽象结构, 它本身不能给出具体的类型. 要说明某个具体的Type (一般由data关键字声明) 是一个 Eq Typeclass. 必须使用 instance 关键字给出 "接口" 的实际定义, 如

1
2
3
4

instance Eq Bool where
  (==) True True = True
  (==) False False = True
  (==) _ _ = False

Functor

Functor(函子) 是一类特殊的Typeclass. 这一术语来自范畴论. 在范畴论中, 函子是两个范畴之间的映射, 它将一个范畴中的对象映射到另一个范畴中的对象, 同时将源范畴中对象之间的态射提升到目标范畴中.

如范畴 \(\mathcal C_1\) 到 范畴 \(\mathcal C_2\) 的函子 \(F\),

\begin{align} A \in \mathrm{Obj}(\mathcal C_1) &\Rightarrow F A \in \mathrm{Obj}(\mathcal C_2) \\\ (f : A \rightarrow B) \in \mathrm{Hom}(A,B) &\Rightarrow F f: F A \rightarrow F B \in \mathrm{Hom}(F A, F B) , A ,B \in \mathrm{Obj}(\mathcal C_1) \\\ F (g \circ f)& = F g \circ F f , f \in \mathrm{Hom}(A,B), g \in \mathrm{Hom}(B,C) \end{align}

对于有一个类型参数的类型, 它将类型映射为新的类型. 但是一般不能将类型与类型之间的函数提升为新的类型之间的函数, 如果能, 它将是Hask 范畴中的函子,也就是 Haskell 中的函子, 该提升操作称之为 fmap. 具体 Functor 的 Haskell定义如下

1
2

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

上述的 f 是带有一个参数的类型构造器. 列表就是最常见的函子, 它的定义如下

1
2
3

instance Functor [] where
  fmap f Nil = Nil
  fmap f (x:xs) = f x : (fmap f xs)

范畴中的函子还要保态射的合成, Haskell 的编译器不会检查这一点, 需要编程人员自行检查.