范畴论与编程：Functor 是什么

引言

你可能每天都在使用 Functor 但你并没有意识到这一点：当你每次使用各种容器类型的 map 方法的时候，其实就是在利用 Functor 的性质

本篇文章会分别从范畴论的视角、编程语言视角讲解 Functor，希望能对你有所帮助 :)

范畴论视角的 Functor

flowchart
    subgraph C
        a
        b
    end
    subgraph D
        fa(F a)
        fb(F b)
    end
    a --> |F| fa(F a)
    b --> |F| fb(F b)
    a --> |f| b
    fa --> |F f| fb

在范畴论的研究里面，Functor $F:\mathcal C\rightarrow\mathcal D$ 指的是是从范畴 $\mathcal C$ 与范畴 $\mathcal D$ 之间的映射关系，并且它是 Structure-Preserving 的。Structure-Preversing 指的是范畴 $\mathcal C$ 的组合关系与恒等映射要保留¹

• 对象映射：在范畴 $\mathcal C$ 里的对象 $a$ 在范畴 $\mathcal D$ 里是 $F\ a$
• 态射映射：在范畴 $\mathcal C$ 里的态射 $f:a\rightarrow b$ 在范畴 $\mathcal D$ 里是 $F\ f:F\ a\rightarrow F\ b$

除此之外，Functor 还需要满足如下的 Functor Laws：

• 恒等态射保留：$F\ id_a=id_{F\ a}$
• 组合关系保留：$F(f\circ g)=(F\ f)\circ(F\ g)$

编程语言（Haskell）视角的 Functor

Haskell 在设计的时候就考虑到了范畴论，因此下面用 Haskell 讲解

用范畴论的视角来看 Haskell，那么所有的 Haskell 类型构成了一个范畴 $\mathcal C$，它的构成是

• 对象：Haskell 类型
• 态射：Haskell 函数

不难知道，从写代码的角度来看，我们关心的是如何定义各种 Haskell 函数，以及不同的 Haskell 类型之间如何做转换。所以只需要了解 $F:\mathcal C\rightarrow\mathcal C$ 这个特殊的 Functor，它也叫做 endofunctor

对象和态射如何映射到 Haskell 里好理解，那么 Functor 如何用 Haskell 代码表示呢？前面提到，Functor 的核心是范畴之间的映射关系，包括对象之间的映射和态射之间的映射

• 对象之间的映射（Haskell 类型之间的映射）：带有 Type Variable 的 Haskell Type Constructor
• 态射之间的映射（Haskell 函数之间的映射）：Haskell Type Class

对象之间的映射好理解，通过带有 Type Variable 的 Type Constructor 就可以从一个类型得到另一个类型，比如 Maybe 类型，给它一个 Int 类型就可以得到 Maybe Int

态射之间的映射可以用下面这个 Functor Type Class 表示

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

Example. Maybe Functor

Haskell 的 Maybe 类型就是一个典型的 Functor，前面已经提到了：任何类型 a 都可以变成 Maybe a，那么它的 fmap 函数要怎么写呢？起码函数签名是清楚的

fmap :: (a -> b) -> Maybe a -> Maybe b

Maybe 类型有 2 种 Data Constructor，分别是 Nothing 和 Just

• Nothing 的意思是什么都没有，那么不管本来是什么函数，映射之后应该都是 Nothing
• Just a 有一个类型为 a 的值，那么从 fmap 的函数签名不难看出应该得到 Just (f b)

代码如下

instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just x) = Just (f x)

那么它符合 Functor 的定义吗？

第一个规律要求 $F\ {id_a}=id_{F\ a}$，即证明 fmap id = id

fmap id Nothing = Nothing
                = id Nothing
-- fmap _ Nothing = Nothing

fmap id (Just x) = Just (id x)
                 = Just x
                 = id (Just x)
-- fmap f (Just x) = Just (f x)

第二个规律要求 $F(f\circ g)=(F\ f)\circ(F\ g)$

fmap (f . g) Nothing = Nothing
                     = fmap f Nothing
                     = fmap f (fmap g Nothing)
                     
fmap (f . g) (Just x) = Just ((f . g) x)
                      = Just (f (g x))
                      = fmap f (Just  (g x))
                      = fmap f (fmap g (Just x))
                      = (fmap f . fmap g) (Just x)

所以我们前面的 fmap 实现是没有问题的

Functor 有什么用？

Functor 在不同的 Haskell 类型之间建立了映射关系，不仅是 Haskell 类型本身，他们之间的 Haskell 函数也被映射过去了。这样的话我们就可以专注于实现某个 Haskell 类型上的函数，最后再通过 Functor 就能用到另外一个 Haskell 类型上。这种场景下， Functor 的角色就是 Adapter

List（表示为 []）是一个典型的 Functor，可以这么定义它的 fmap 函数

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

假设有一个 Int 列表：[Int]，你已经实现了在 Int 上的一个运算操作 foo，如下所示

foo :: Int -> Int
foo x = (x * 2) + 1

现在想要对 [Int] 列表的每一个元素执行上面的操作，你并不需要重新写处理逻辑，只需要 fmap 一下

fmap foo [1, 2, 3]
-- [3, 5, 7]

用 List Functor 作为例子有点 trivial 了，但其实背后的思想是类似的 :)