Category Theory Translation of Category Theory for Programmers

1.7 Functors - 函子

1.7 Functors - 函子

Link to Blog

<译> 函子

Functors - 函子

函子是范畴之间的映射。给定两个范畴C与D，函子F可以将C中的对象映射为D中的对象，可以将C中态射映射为D中态射，并保持其结构。若C中有对象a，它在D中的象为Fa；C中有从对象a到b的态射f，其在D中的象为Ff，从Fa到Fb。此外，态射的复合也应当符合直觉的，在范畴C中h是g与f的复合，那么在范畴D中，Fh应当是Fg与Ff的复合。最后，C中的恒等态射被映射为D中的恒等态射。$Fid_a = id_{Fa}$ (F ida = idFa) ida 是作用于对象a的恒等态射，idFa是作用于对象Fa的恒等态射。

函子比常规函数的约束更为严格，函子必须保持范畴的结构。

函子可以做折叠或嵌入的工作。所谓嵌入，就是将一个小的源范畴嵌入到更大的目标范畴中。一个极端的例子，源范畴是个单例范畴——只有一个对象与一个态射（恒等态射）的范畴，从单例范畴映射到任何其他范畴的函子，所做的工作就是在后者中选择一个对象。这完全类似于接受单例集合的态射，这个态射会从目标集合中选择元素。最巨大的折叠函子被称为常函子$\triangle_C$，它将源范畴中的每个对象映射为目标范畴中特定的对象 c，它也可以将源范畴中的每个态射映射为目标范畴中的特定的恒等态射$id_c$，它在行为上像一个黑洞，将所有东西压成一个奇点。在讨论极限与余极限时，我们再来考察这个黑洞函子。

Functors in Programming - 编程中的函子

functors that map this category into itself — such functors are called endofunctors.

函子将这个范畴映射为其自身——这样的函子被称为自函子。

Maybe Functor - Maybe 函子

Maybe 的定义就是将类型 a 映射为类型 Maybe a：data Maybe a = Nothing | Just a。

Maybe 本身不是一个类型，它是一个类型构造子（Constructor）。必须向它提供一个类型参数，例如 Int 或 Bool，然后才可以使其变成一个类型。如不果不向 Maybe 提供任何参数，那么它就是一个作用于类型的函数。

一个函子不仅仅只映射对象（在此，是类型），它也映射态射（在此，是函数）。对于任何从 a 到 b 的函数：f :: a -> b被 Maybe 函子映射为：f' :: Maybe a -> Maybe b。Haskell 以高阶函数的形式实现了一个函子的态射映射部分，这个函数叫 fmap。对于 Maybe 的情况，这个函数的签名如下：fmap :: (a -> b) -> (Maybe a -> Maybe b)。通常说fmap提升（Lift）了一个函数。被提升的函数作用于 Maybe 层次上的值。

为了说明类型构造子 Maybe 携同函数 fmap 共同形成一个函子，不得不证明 fmap 能够维持恒等态射以及态射的复合的存在。所证明的东西，叫做『函子定律』。凡是满足函子定律的函子，必定不会破坏范畴的结构。

Equational Reasoning - 等式推导

为了证明函子定律，我需要借助等式推导，这也是 Haskell 中常用的证明技巧。它利用了 Haskell 函数基于等式定义这一优势：左侧等于右侧。总是可以用其中一侧替换另一侧，只是有时变量名需要改一下以避免名字冲突。可以将这种替换视为内联一个函数，或者将一个表达式重构为一个函数。这种替换可以从两个方向进行，如果一个函数是基于模式匹配定义的，可以单独使用它的子定义。

先从证明函子对恒等态射的维持开始：fmap id = id。要考虑两种情况：Nothing 与 Just。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

  fmap id Nothing 
= { definition of fmap }
  Nothing 
= { definition of id }
  id Nothing

  fmap id (Just x) 
= { definition of fmap }
  Just (id x) 
= { definition of id }
  Just x
= { definition of id }
  id (Just x)

现在来证明 fmap 能够维持态射的复合：fmap (g . f) = fmap g . fmap f

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

  fmap (g . f) Nothing 
= { definition of fmap }
  Nothing 
= { definition of fmap }
  fmap g Nothing
= { definition of fmap }
  fmap g (fmap f Nothing)

  fmap (g . f) (Just x)
= { definition of fmap }
  Just ((g . f) x)
= { definition of composition }
  Just (g (f x))
= { definition of fmap }
  fmap g (Just (f x))
= { definition of fmap }
  fmap g (fmap f (Just x))
= { definition of composition }
  (fmap g . fmap f) (Just x)

Optional

Maybe一般其它语言中一般是Optional来实现。给出C++中的伪实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

template<class T>
class optional {
    bool _isValid; // the tag
    T    _v;
public:
    optional()    : _isValid(false) {}         // Nothing
    optional(T x) : _isValid(true) , _v(x) {}  // Just
    bool isValid() const { return _isValid; }
    T val() const { return _v; }
};

// fmap - v1
template<class A, class B>
std::function<optional<B>(optional<A>)> 
fmap(std::function<B(A)> f) 
{
    return [f](optional<A> opt) {
        if (!opt.isValid())
            return optional<B>{};
        else
            return optional<B>{ f(opt.val()) };
    };
}

// fmap -v2
template<class A, class B>
optional<B> fmap(std::function<B(A)> f, optional<A> opt) {
    if (!opt.isValid())
        return optional<B>{};
    else
        return optional<B>{ f(opt.val()) };
}

Type Class - 类型类

Haskell使用类型类对函子进行抽象。一个类型类定义了支持一个公共接口的类型族。例如，支持相等谓词的类型类如下

1
2

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

这个定义陈述的是，如果类型 a 支持 (==) 运算符，那么它就是 Eq 类。(==) 运算符接受两个类型为 a 的值，返回 Bool 值。如果你想告诉 Haskell 有一个特定的类型是 Eq 类，那么你不得不将其声明为这个类的一个实例，并提供 (==) 的实现。例如，一个二维 Point（两个 Float 的积类型）：data Point = Pt Float Float 需要为它定义相等谓词：

1
2

instance Eq Point where
    (Pt x y) == (Pt x' y') = x == x' && y == y'

这里将 (==) 作为中缀运算符使用，它处于 (Pt x y) 与 (Pt x’ y’) 之间，而函数体是单个 = 号后面的部分。一旦将 Point 声明为 Eq 的一个实例，你就可以直接比较点与点是否相等了。注意，与 C++ 或 Java 不同，在定义 Point 的时候不必指定它是 Eq 类（或接口）的实例——可在真正需要的时候再指定。

类型类是 Haskell 仅有的函数（运算符）重载机制。在为不同的函子重载 fmap 时需要借助类型类，尽管有一个难点：函子不能作为类型来定义，只能作为类型的映射来定义，即类型构造子。我们需要一个由类型构造子构成的族，而不是像 Eq 这样的类型族。所幸，Haskell 的类型类可以将类型构造子像类型那样来处理。因此，Functor 类的定义如下：

1
2

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

如果存在符合上述签名的 fmap 函数，这个类规定了 f 是一个 Functor。小写的 f 是一个类型变量，类似于类型变量 a 与 b，然而编译器能够推断出它是一个类型构造子，而不是一个类型，依据是它的用途：作用于其他类型，即 f a 与 f b。因此，要声明一个 Functor 的实例时，你不得不给它一个类型构造子，对于 Maybe 而言就是：

1
2
3

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

顺便说一下，Functor 类，以及它的一些实例，这些实例是为大多数简单的数据类型而定义的，包括 Maybe，它们都是 Haskell 标准库的一部分。

Functor in C++ 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

template<template<class> F, class A, class B>
F<B> fmap(std::function<B(A)>, F<A>);

// error! -  C++ 中是禁止模板函数的部分特化
template<class A, class B>
optional<B> fmap<optional>(std::function<B(A)> f, optional<A> opt)

// - 只能这样实现
template<class A, class B>
optional<B> fmap(std::function<B(A)> f, optional<A> opt) 
{
    if (!opt.isValid())
        return optional<B>{};
    else
        return optional<B>{ f(opt.val()) };
}

List Functor

data List a = Nil | Cons a (List a) List 是类型构造子，它将任意类型 a 映射为类型 List a。为了表明 List 是一个函子，我们不得不定义一个提升函数：接受一个 a -> b 的函数，产生一个 List a -> List b 的函数：fmap :: (a -> b) -> (List a -> List b) 列表函子的实例声明：

1
2
3

instance Functor List where
    fmap _ Nil = Nil
    fmap f (Cons x t) = Cons (f x) (fmap f t)

Reader Functor

已经对函子获得一些直觉了——例如，函子是某种容器。下面来个有点烧脑的例子，考虑一个从类型 a 到一个返回 a 的函数类型的映射。

在 Haskell 中，函数类型是使用箭头类型构造子 (->) 构造出来的，这个类型构造子接受两种类型：参数类型与返回类型。你已经见过这个类型构造子的中缀形式 a -> b，但是也可以写成前缀形式，像是被参数化了：(->) a b。就像常规的函数一样，接受多个参数的类型函数可以偏应用。因此，当我们向箭头只提供一个参数时，它依然期待另一个参数的出现。因此 (->) a也是个类型构造子。它需要一个类型 b 来产生完整的类型 a -> b。它所表示的是，它定义了一族由 a 参数化的类型构造子。

处理两个类型参数可能有点混乱，先做一些重命名的工作。在我们之前的函子定义中，我们可以将参数类型称为 r，将返回类型称为 a。因此我们的类型构造子可以接受任意类型 a，并将其映射为类型 r -> a。为了表明它是个函子，我们就需要一个函数，它可以将函数 a ->b 提升为一个从 r -> a 到 r -> b 的函数，而 r -> a 与 r -> b 就是 (->) r 这个类型构造子分别作用于 a 与 b 所产生的函数类型。以上讨论最终可归结为 fmap 的函数签名：fmap :: (a -> b) -> (r -> a) -> (r -> b) 解决一个难题：对于给定的函数 f :: a -> b 与 g :: r -> a，构造一个函数 r -> b。这是复合两个函数的唯一途径，也恰恰就是我们需要的。因此，我们需要将 fmap 的实现为：

1
2

instance Functor ((->) r) where
    fmap f g = f . g

就是我们想要的 fmap，紧凑些的表示fmap f g = (.) f g ，甚至 fmap = (.)

类型构造子 (->) r 与上面这个 fmap 组合起来所形成的函子被称为 Reader 函子。

Functors as Containers - 函子作为容器

纯函数是可以被保存下来的，函数的执行结果被扔到可检索的表中，而表是数据。 Haskell 具有惰性计算能力，一个传统的容器，譬如一个列表，实际上可以被实现为一个函数。例如，一个包含自然数的无限长的列表，可被定义为：nats :: [Integer] = [1..] 显然，一个无限长的列表是不能存储在内存中的。编译器将其实现为一个可以按需产生一组 Integer 值的函数。Haskell 有效的模糊了数据与代码的区别。可以将列表视为函数，也可以将函数视为从存储着参数与结果的表中查询数据。如果函数的定义域有界并且不太大，将函数变成表查询是完全可行的。

将函子对象（由自函子产生的类型的实例）视为包含着一个值或多个值的容器，即使这些值实际上并未出场。C++ 中的 std::future 函子在某些时间点上可以存储一个值，但是它不能担保这个值总是存在；如果你想访问这个值，可能会受阻，直到其它线程的计算过程。另一个例子是 Haskell 的 IO 对象，它包含着用户的输入，或者是我们的宇宙要显示于屏幕上的『Hello World!』的未来版本。根据这种解释，函子对象就是可以包含一个值或多个值的容器，这些值的类型参数化了函子对象。或者，函子对象可能包含产生这些值的方法。我们根本不关心能否访问这些值——这些事发生在函子作用范围之外。如果函子对象包含的值能够被访问，我们就可以看到相应的操作结果；如果它们不能被访问，我们所关心的只是操作的正确复合，以及伴随不改变任何事物的恒等函数的操作。

为了向你表明我们是如何的不关心函子对象内部的值，这里有一个类型构造子，它完全的忽略参数 a：data Const c a = Const c Const 类型构造子接受两种类型， c 与 a。就像我们处理箭头构造子那样，我们对其进行偏应用从而制造了一个函子。数据构造子（也叫 Const）仅接受 c 类型的值，它不依赖 a。与这种类型构造子相配的 fmap 类型为：fmap :: (a -> b) -> Const c a -> Const c b 因为这个函子是忽略类型参数的，所以 fmap 的实现也可以自由忽略那个函数参数——因为这个函数无事可做：

1
2

instance Functor (Const c) where
    fmap _ (Const v) = Const v

在 C++ 中可能更清晰一些，因为 C++ 中在类型参数与值之间有着明显的区别，前者出现于编译期间，后者出现于运行时：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

template<class C, class A>
struct Const {
    Const(C v) : _v(v) {}
    C _v;
};

template<class C, class A, class B>
Const<C, B> fmap(std::function<B(A)> f, Const<C, A> c) {
    return Const<C, B>{c._v};
}

尽管它有些怪异，但是 Const 函子在许多结构中扮演着重要的角色。在范畴论中，它是$\triangle_C$函子的特例，后者我们在前面提到过的，就是那个黑洞函子，而 Const 是个黑洞自函子。

Functor Composition

函子的复合类似于集合之间的函数复合。两个函子的复合，就是两个函子分别对各自的对象进行映射的复合，对于态射也是这样。恒等态射穿过两个函子之后，它还是恒等态射。复合的态射穿过两个函子之后还是复合的态射。自函子很容易复合。

1
2
3

maybeTail :: [a] -> Maybe [a]
maybeTail [] = Nothing
maybeTail (x:xs) = Just xs

maybeTail 返回的结果是两个作用于 a 的函子 Maybe 与 [] 复合后的类型。这些函子，每一个都配备了一个 fmap，但是如果我们想将一个函数 f 作用于复合的函子 Maybe [] 所包含的内容，该怎么做？我们不得不突破两层函子的封装：使用 fmap 突破 Maybe，再使用 fmap 突破列表。例如，要对一个 Maybe [Int] 中所包含的元素求平方，可以这样做：

1
2
3
4
5
6

square x = x * x

mis :: Maybe [Int]
mis = Just [1, 2, 3]

mis2 = fmap (fmap square) mis

经过类型分析，对于外部的 fmap，编译器会使用 Maybe 版本的；对于内部的 fmap，编译器会使用列表版本的。于是，上述代码也可以写为：mis2 = (fmap . fmap) square mis 要记住，fmap 可以看作是只接受一个参数的函数： fmap :: (a -> b) -> (f a -> f b) 示例中，(fmap . fmap) 中的第 2 个 fmap 所接受的参数是： square :: Int -> Int 然后返回一个这种类型的函数： [Int] -> [Int] 第一个 fmap 接受这个函数，然后再返回一个函数： Maybe [Int] -> Maybe [Int] 最终，这个函数作用于 mis。因此两个函子的复合结果，依然是函子，并且这个函子的 fmap 是那两个函子对应的 fmap 的复合。

现在回到范畴论：显然函子的复合是遵守结合律的，因为对象的映射遵守结合律，态射的映射也遵守结合律。在每个范畴中也有一个恒等函子：它将每个对象都映射为其自身，将每个态射映射为其自身。因此在某个范畴中，函子具有与态射相同的性质。什么范畴会是这个样子？必须得有一个范畴，它包含的对象是范畴，它包含的态射是函子。也就是说，它是范畴的范畴。但是，所有范畴的范畴不得不包含它自身，这样我们就陷入了自相矛盾的境地，就像不可能存在集合的集合那样。然而，有一个叫做 Cat 的范畴，它包含了所有的小范畴。这个范畴是一个大的范畴，因此它就不可能是它自身的成员。所谓的小范畴，就是它包含的对象可以形成一个集合，而不是某种比集合还大的东西。请注意，在范畴论中，即使一个无限的不可数的集合也被认为是『小』的。我想我已经提到过这样的集合了，因为我们已经看过同样的结构在许多抽象层次上的重复出现。以后我们也会看到函子也能形成范畴。

Challenge 

1

let fmap = (<<)