范畴，态射和函子

这篇聊聊函数式编程语言所依赖的一些基础概念。这些概念所以难懂，乃是层层抽象所致；而也是因为抽象，才得以用最基本的规则描述最复杂的事物。

范畴和函子

我们都知道集合，对应到程序语言里，可以认为一个类型就代表了一个集合。比如说Int表示所有的整数，Char表示所有的字符，String表示所有的字符串，等等。类的实例构成了集合中的元素，比如整数1是集合Int里的元素，'H'是集合Char里的元素，"Hello"是集合String里的元素。

可以把一个集合映射到另一个集合，比如说IntToStr :: Int -> String把整数转成字符串。这样的映射就是函数。

那么，能不能把上面提到的集合，以及集合到集合的映射，打包在一起描述？

当然可以，这就是范畴（category），范畴中的元素被称为物体（object），物体既可以是类型，也可以是值，或者是另一个范畴。

举例来说，我们可以把Int和String这两个集合组成一个范畴，函数IntToStr :: Int -> String描述了这两个物体之间的关系。物体和态射是范畴中两个基本组成。像Haskell这样的程序语言，其所有的类型组成了一个巨大的范畴，而函数则定义了不同物体（类型，值，或者范畴）间的态射。

好，那有没有办法把一个范畴转换成另一个范畴？比方说Maybe这个范畴，用来表示一个值存在（例如Just 10）或者不存在（Nothing），怎么把范畴{Int, String}转换成{Maybe[Int], Maybe[String]}呢？

有人说，那简单，提供两个构造函数，使得我们可以写Maybe(1), Maybe("Hello")，不就可以了吗？但不要忘了，范畴是由物体和态射组成的，构造函数只解决了物体到物体的映射，没有解决态射到态射的映射。上面的例子，我们可以提供这样一个函数fmap,

instance Functor Maybe where
	fmap func (Just a) = Just (func a)
	fmap _ Nothing     = Nothing

其中的func就可以是IntToStr :: Int -> String，比如我们可以写

Prelude> fmap IntToStr (Just 10)
Just "10"

尽管IntToStr原本是作用在Int所在的范畴的，但通过fmap我们把它转换到了Maybe范畴。包含了这种fmap函数的类型（比如上面的Maybe），称之为函子（functor)，它完整实现了从另一个范畴到自己的转换（包含了对物体和态射的转换）。更一般的，函子f被定义为

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

应用函子

但态射有时候不一定是从一个类型到另一个类型这么简单，假设我们有一个Curry函数replicate :: Int -> Char -> String可以把Char重复Int次得到一个String，问题来了，怎么把它应用到新的范畴Maybe上，给定Maybe Int和Maybe Char，得到Maybe String呢？

我们先试着应用一下Maybe的fmap，Int -> Char -> String可以看作是Int -> (Char -> String)，其中Int对应a，Char -> String对应b，

fmap replicate
	:: Maybe Int -> Maybe (Char -> String)

我们现在给它一个Maybe Int类型，比如Just 10，

fmap replicate Just 10
	:: Maybe (Char -> String)

别忘了我们的目标是，

给定Maybe Int和Maybe Char，得到Maybe String

我们刚才已经给了Maybe Int，现在还差Maybe Char -> Maybe String。怎么从fmap replicate Maybe Int :: Maybe (Char -> String)变过去呢？

很简单，再弄一个函数嘛，

apply :: Maybe (Char -> String) -> Maybe Char -> Maybe String

apply fmap replicate Just 10
	:: Maybe Char -> Maybe String

这就搞定了，现在喂给它一个Maybe Char类型，比如Just 'x'，

Prelude> apply fmap replicate Just 10 Just 'x' :: Maybe String
Just 'xxxxxxxxxx'

通过apply fmap replicate，我们实现了把原范畴中的态射replicate :: Int -> Char -> String转换成了Maybe范畴中的态射Maybe Int -> Maybe Char -> Maybe String，而且这个apply函数可以嵌套使用，来实现任意参数态射到新范畴的转换：apply (apply (...) ...) fmap func_in_orig_category。

实现了这种apply函数的类型（比如上面的Maybe），被称为应用函子（applicative functor），在Haskell为了方便书写，这个过程被写成了中缀函数<*>，

class Functor f => Applicative f where
	(<*>) :: f (a -> b) -> f a -> f b

范畴和函子

应用函子

Enjoy Reading This Article?