第 8 章：函子性（Functoriality）

原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 8. 原书 PDF、.tex 源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。

现在你已经知道函子是什么，也见过了一些例子，接下来看看如何用较小的函子构造较大的函子。特别有趣的是，哪些类型构造器（它们对应范畴中对象之间的映射）可以扩展为函子（也就是还包含态射之间的映射）。

8.1 双函子（Bifunctors）

既然函子是 $Cat$（范畴的范畴）中的态射，那么很多关于态射，特别是关于函数的直觉，也适用于函子。例如，正如可以有两个参数的函数，也可以有两个参数的函子，也就是双函子。在对象层面，双函子把一对对象映射到范畴 $E$ 中的一个对象；这一对对象中，一个来自范畴 $C$，另一个来自范畴 $D$。注意，这其实就是说，它是从范畴的笛卡尔积 C x D 到 $E$ 的映射。

这很直接。但函子性意味着双函子也必须映射态射。不过这一次，它必须把一对态射映射到 $E$ 中的一个态射；这一对态射中，一个来自 $C$，另一个来自 $D$。

同样，一对态射也只是乘积范畴 C x D 中的一个态射。我们把范畴笛卡尔积中的态射定义为一对态射，它们从一对对象指向另一对对象。这些态射对可以用显然的方式组合：

(f, g) . (f', g') = (f . f', g . g')

这个组合满足结合律，并且有恒等态射，也就是一对恒等态射 (id, id)。所以范畴的笛卡尔积确实是一个范畴。

理解双函子的一种更简单方式，是把它看作分别在每个参数上都是函子。因此，与其把函子律，也就是结合律和恒等保持，从函子翻译到双函子上，不如分别检查每个参数上的函子性。不过一般来说，分别函子性并不足以证明联合函子性。联合函子性失败的范畴称为预幺半范畴（premonoidal category）。

在 Haskell 中定义双函子。这里三个范畴都是同一个范畴：Haskell 类型范畴。双函子是接受两个类型参数的类型构造器。下面是直接取自 Control.Bifunctor 库的 Bifunctor 类型类定义：

class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d
    bimap g h = first g . second h

    first :: (a -> c) -> f a b -> f c b
    first g = bimap g id

    second :: (b -> d) -> f a b -> f a d
    second = bimap id

trait Bifunctor[F[_, _]] {
  def bimap[A, B, C, D](g: A => C)(h: B => D): F[A, B] => F[C, D] =
    first(g) compose second(h)

  def first[A, B, C](g: A => C): F[A, B] => F[C, B] =
    bimap(g)(identity[B])

  def second[A, B, D](h: B => D): F[A, B] => F[A, D] =
    bimap(identity[A])(h)
}

类型变量 f 表示双函子。可以看到，在所有类型签名中，它总是应用于两个类型参数。第一个类型签名定义了 bimap：一次映射两个函数。结果是一个提升后的函数 (f a b -> f c d)，作用于由双函子的类型构造器生成的类型。bimap 有一个基于 first 和 second 的默认实现。（如前所述，这并不总能工作，因为这两个映射可能不交换，也就是说 first g . second h 不一定等于 second h . first g。）

另外两个类型签名 first 和 second，分别是见证 f 在第一个参数和第二个参数上具有函子性的两个 fmap。

类型类定义还为二者提供了基于 bimap 的默认实现。声明 Bifunctor 实例时，可以选择实现 bimap 并接受 first 与 second 的默认实现；也可以实现 first 和 second，接受 bimap 的默认实现。当然，你也可以三个都实现，但这时就由你来确保它们彼此满足这种关系。

8.2 积与余积双函子（Product and Coproduct Bifunctors）

双函子的一个重要例子是范畴积，也就是通过通用构造定义的两个对象的积。如果任意一对对象都有积，那么从这对对象到其积的映射就是双函子性的。这一点一般成立，在 Haskell 中尤其如此。下面是 pair 构造器的 Bifunctor 实例；pair 是最简单的积类型：

instance Bifunctor (,) where
    bimap f g (x, y) = (f x, g y)

implicit val tuple2Bifunctor = new Bifunctor[Tuple2] {
  override def bimap[A, B, C, D](f: A => C)(g: B => D): ((A, B)) => (C, D) = {
    case (x, y) => (f(x), g(y))
  }
}

这里没有太多选择：bimap 只是把第一个函数应用到 pair 的第一个分量，把第二个函数应用到第二个分量。给定类型之后，代码几乎会自己写出来：

bimap :: (a -> c) -> (b -> d) -> (a, b) -> (c, d)

def bimap[A, B, C, D](f: A => C)(g: B => D): ((A, B)) => (C, D)

这个双函子的作用是构造类型对，例如：

(,) a b = (a, b)

由对偶性可知，如果一个范畴中任意一对对象都有余积，那么余积也是双函子。在 Haskell 中，这体现为 Either 类型构造器是 Bifunctor 的实例：

instance Bifunctor Either where
    bimap f _ (Left x) = Left (f x)
    bimap _ g (Right y) = Right (g y)

implicit val eitherBifunctor = new Bifunctor[Either] {
  override def bimap[A, B, C, D](f: A => C)(g: B => D): Either[A, B] => Either[C, D] = {
    case Left(x) => Left(f(x))
    case Right(y) => Right(g(y))
  }
}

这段代码同样几乎会自己写出来。

还记得我们讨论幺半范畴的时候吗？幺半范畴定义了一个作用在对象上的二元运算，以及一个单位对象。我提过，$Set$ 关于笛卡尔积是一个幺半范畴，单位对象是单元素集合；关于不交并，它也是一个幺半范畴，单位对象是空集。我没有提到的是，幺半范畴的要求之一，是这个二元运算必须是一个双函子。这是一个非常重要的要求：我们希望幺半积与由态射定义的范畴结构相容。现在，我们距离幺半范畴的完整定义又近了一步（在到达那里之前，还需要学习自然性）。

8.3 函子性的代数数据类型（Functorial Algebraic Data Types）

我们已经见过若干参数化数据类型的例子，它们后来都被证明是函子，也就是说，我们能够为它们定义 fmap。复杂数据类型由更简单的数据类型构造而来。特别是，代数数据类型（ADT）使用和与积创建。我们刚刚看到，和与积都是函子性的。我们也知道函子可以组合。所以，如果能证明 ADT 的基本构件是函子性的，就能知道参数化 ADT 也是函子性的。

那么，参数化代数数据类型的构件是什么？首先，有些项不依赖函子的类型参数，例如 Maybe 中的 Nothing，或 List 中的 Nil。它们等价于 Const 函子。记住，Const 函子会忽略自己的类型参数（准确地说，是第二个类型参数，也就是我们关心的那个；第一个类型参数保持常量）。

然后，还有一些元素只是简单封装类型参数本身，例如 Maybe 中的 Just。它们等价于恒等函子。我之前提到过恒等函子，它是 Cat 中的恒等态射，但当时没有给出它在 Haskell 中的定义。下面就是：

data Identity a = Identity a

type Id[A] = A

instance Functor Identity where
    fmap f (Identity x) = Identity (f x)

implicit val identityFunctor = new Functor[Id] {
  def fmap[A, B](f: A => B)(x: Id[A]): Id[B] =
    f(x)
}

可以把 Identity 看作最简单的容器，它总是只存储一个 a 类型的（不可变）值。

代数数据结构中的其他一切，都是用积与和从这两个原语构造出来的。

有了这些新知识，再重新看看 Maybe 类型构造器：

data Maybe a = Nothing | Just a

sealed trait Option[+A]
case object None extends Option[Nothing]
case class Some[A](a: A) extends Option[A]

它是两个类型的和，而我们现在知道和是函子性的。第一部分 Nothing 可以表示为作用在 a 上的 Const ()（Const 的第一个类型参数被设置为 unit；稍后会看到 Const 更有趣的用法）。第二部分只是恒等函子的另一个名字。我们可以在同构意义下把 Maybe 定义为：

type Maybe a = Either (Const () a) (Identity a)

type Option[A] = Either[Const[Unit, A], Id[A]]

所以 Maybe 是双函子 Either 与两个函子 Const () 和 Identity 的组合。（Const 实际上也是双函子，但这里总是以部分应用的形式使用它。）

我们已经见过函子的组合仍然是函子。很容易相信，对双函子来说同样成立。我们只需要弄清楚双函子与两个函子的组合在态射上如何工作。给定两个态射，我们用一个函子提升其中一个，用另一个函子提升另一个。然后把得到的一对已提升态射，再用双函子提升。

可以在 Haskell 中表达这种组合。定义一个数据类型，它由一个双函子 bf 参数化（这是一个类型变量，表示接受两个类型作为参数的类型构造器）、两个函子 fu 和 gu 参数化（它们都是各自接受一个类型变量的类型构造器），以及两个普通类型 a 和 b 参数化。我们把 fu 应用到 a，把 gu 应用到 b，然后把 bf 应用到得到的两个类型上：

newtype BiComp bf fu gu a b = BiComp (bf (fu a) (gu b))

case class BiComp[BF[_, _], FU[_], GU[_], A, B](v: BF[FU[A], GU[B]])

这是对象，也就是类型上的组合。注意，在 Haskell 中，我们把类型构造器应用到类型上，就像把函数应用到参数上一样。语法也是一样的。

如果你有点迷路，试着依次把 BiComp 应用到 Either、Const ()、Identity、a 和 b。你会得到我们那个最精简版本的 Maybe b（其中 a 被忽略）。

新数据类型 BiComp 在 a 和 b 上是双函子，但前提是 bf 本身是 Bifunctor，并且 fu 和 gu 都是 Functor。编译器必须知道 bf 有可用的 bimap 定义，也必须知道 fu 和 gu 有可用的 fmap 定义。在 Haskell 中，这会作为实例声明中的前置条件来表达：一组类约束，后面跟着双箭头：

instance (Bifunctor bf, Functor fu, Functor gu) =>
    Bifunctor (BiComp bf fu gu) where
        bimap f1 f2 (BiComp x) =
            BiComp ((bimap (fmap f1) (fmap f2)) x)

implicit def bicompBiFunctor[
  BF[_, _], FU[_], GU[_]](
  implicit BF: Bifunctor[BF],
  FU: Functor[FU],
  GU: Functor[GU]) = {

  type BiCompAB[A, B] = BiComp[BF, FU, GU, A, B]

  new Bifunctor[BiCompAB] {
    override def bimap[A, B, C, D](f1: A => C)(f2: B => D): BiCompAB[A, B] => BiCompAB[C, D] = {
      case BiComp(x) =>
        BiComp(
          BF.bimap(FU.fmap(f1))(GU.fmap(f2))(x)
        )
    }
  }
}

BiComp 的 bimap 实现基于 bf 的 bimap，以及 fu 和 gu 的两个 fmap。只要使用 BiComp，编译器就会自动推断所有类型，并选择正确的重载函数。

bimap 定义中的 x 具有如下类型：

bf (fu a) (gu b)

BF[FU[A], GU[B]]

这个类型相当拗口。外层的 bimap 穿过外层 bf，两个 fmap 分别钻到 fu 与 gu 下面。如果 f1 和 f2 的类型是：

f1 :: a -> a'
f2 :: b -> b'

def f1: A => A1
def f2: B => B1

那么最终结果的类型就是 bf (fu a') (gu b')：

bimap :: (fu a -> fu a') -> (gu b -> gu b')
      -> bf (fu a) (gu b) -> bf (fu a') (gu b')

def bimap: (FU[A] => FU[A1]) => (GU[B] => GU[B1]) =>
  BiComp[BF, FU, GU, A, B] => BiComp[BF, FU, GU, A1, B1]

如果你喜欢拼图，这类类型操作可以提供好几个小时的娱乐。

因此，我们其实不必证明 Maybe 是函子。这个事实来自它的构造方式：它是两个函子性原语的和。

敏锐的读者可能会问：如果为代数数据类型推导 Functor 实例如此机械化，难道不能自动化，让编译器来做吗？确实可以，而且已经是这样。你需要在源文件顶部加入下面这一行，以启用特定的 Haskell 扩展：

{-# LANGUAGE DeriveFunctor #-}

然后给数据结构加上 deriving Functor：

data Maybe a = Nothing | Just a deriving Functor

相应的 fmap 就会由编译器为你实现。

代数数据结构的规则性，不仅让推导 Functor 实例成为可能，也让推导其他若干类型类的实例成为可能，包括前面提到的 Eq 类型类。还可以教编译器推导你自己的类型类实例，不过那更高级一些。但思想相同：你为基本构件以及和与积提供行为，然后让编译器推导其余部分。

8.4 C++ 中的函子（Functors in C++）

如果你是 C++ 程序员，那么在实现函子方面显然只能靠自己。不过，你应该能够在 C++ 中识别某些代数数据结构。如果这种数据结构被做成泛型模板，你应该能够很快为它实现 fmap。

看看树这种数据结构，在 Haskell 中可以把它定义为递归和类型：

data Tree a = Leaf a | Node (Tree a) (Tree a)
    deriving Functor

sealed trait Tree[+A]
case class Leaf[A](a: A) extends Tree[A]
case class Node[A](l: Tree[A], r: Tree[A]) extends Tree[A]
// implicit def treeFunctor = ???

如前所述，在 C++ 中实现和类型的一种方式是使用类层次结构。在面向对象语言中，把 fmap 实现为基类 Functor 的虚函数，然后在所有子类中重写它，似乎很自然。不幸的是，这是不可能的，因为 fmap 是模板。它不仅由它所作用的对象类型（this 指针）参数化，也由应用到对象上的函数的返回类型参数化。C++ 中虚函数不能模板化。我们会把 fmap 实现为泛型自由函数，并用 dynamic_cast 取代模式匹配。

为了支持动态类型转换，基类至少必须定义一个虚函数，所以把析构函数设为虚函数（无论如何这都是好主意）：

template<class T>
struct Tree {
    virtual ~Tree() {};
};

Leaf 只是伪装成树节点的 Identity 函子：

template<class T>
struct Leaf : public Tree<T> {
    T _label;
    Leaf(T l) : _label(l) {}
};

Node 是一个积类型：

template<class T>
struct Node : public Tree<T> {
    Tree<T> * _left;
    Tree<T> * _right;
    Node(Tree<T> * l, Tree<T> * r) : _left(l), _right(r) {}
};

实现 fmap 时，我们利用对 Tree 类型的动态分派。Leaf 情形应用 Identity 版本的 fmap，Node 情形则被看作一个双函子与两份 Tree 函子的组合。作为 C++ 程序员，你可能不习惯用这些术语分析代码，但这是一次很好的范畴式思维练习。

template<class A, class B>
Tree<B> * fmap(std::function<B(A)> f, Tree<A> * t) {
    Leaf<A> * pl = dynamic_cast <Leaf<A>*>(t);
    if (pl)
        return new Leaf<B>(f (pl->_label));

    Node<A> * pn = dynamic_cast<Node<A>*>(t);
    if (pn)
        return new Node<B>( fmap<A>(f, pn->_left)
                          , fmap<A>(f, pn->_right));
    return nullptr;
}

为简单起见，我决定忽略内存与资源管理问题，但在生产代码中，你很可能会使用智能指针（唯一指针或共享指针，取决于你的策略）。

把它和 Haskell 中的 fmap 实现比较一下：

instance Functor Tree where
    fmap f (Leaf a) = Leaf (f a)
    fmap f (Node t t') = Node (fmap f t) (fmap f t')

implicit val treeFunctor = new Functor[Tree] {
  def fmap[A, B](f: A => B)(fa: Tree[A]): Tree[B] = fa match {
    case Leaf(a) => Leaf(f(a))
    case Node(t, t1) => Node(fmap(f)(t), fmap(f)(t1))
  }
}

这个实现同样可以由编译器自动推导。

8.5 Writer 函子（The Writer Functor）

我曾承诺会回到前面描述过的 Kleisli 范畴。那个范畴中的态射表示为返回 Writer 数据结构的“修饰过的”函数。

type Writer a = (a, String)

type Writer[A] = (A, String)

我说过，这种修饰以某种方式与自函子有关。确实，Writer 类型构造器在 a 上是函子性的。我们甚至不需要为它实现 fmap，因为它只是一个简单的积类型。

但一般来说，Kleisli 范畴和函子之间是什么关系？Kleisli 范畴既然是范畴，就定义了组合和恒等。提醒一下，组合由鱼运算符给出：

(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)
m1 >=> m2 = \x ->
    let (y, s1) = m1 x
        (z, s2) = m2 y
    in (z, s1 ++ s2)

object kleisli {
  // allows us to use >=> as an infix operator
  implicit class KleisliOps[A, B](m1: A => Writer[B]) {
    def >=>[C](m2: B => Writer[C]): A => Writer[C] =
      x => {
        val (y, s1) = m1(x)
        val (z, s2) = m2(y)
        (z, s1 + s2)
      }
  }
}

恒等态射则由名为 return 的函数给出：

return :: a -> Writer a
return x = (x, "")

// return is a keyword in Scala
def pure[A](x: A): Writer[A] = (x, "")

事实证明，如果你盯着这两个函数的类型看得足够久（我的意思是真的足够久），就能找到一种方式把它们组合起来，生成一个具有正确类型签名、可以充当 fmap 的函数。如下：

fmap f = id >=> (\x -> return (f x))

import kleisli._

def fmap[A, B](f: A => B): Writer[A] => Writer[B] =
  identity[Writer[A]] _ >=> (x => pure(f(x)))

这里，鱼运算符组合了两个函数：一个是熟悉的 id，另一个是 lambda，它先把 f 作用到 lambda 参数上，再对结果应用 return。最难绕过来的地方可能是 id 的使用。鱼运算符的参数难道不应该是接受“普通”类型并返回修饰类型的函数吗？其实不然。没有人说 a -> Writer b 中的 a 必须是“普通”类型。它是类型变量，所以可以是任何东西，尤其可以是像 Writer b 这样的修饰类型。

所以 id 会接受 Writer a 并把它变成 Writer a。鱼运算符会从中钓出 a 的值，并把它作为 x 传给 lambda。在 lambda 中，f 会把它变成 b，而 return 会给它加上修饰，使它成为 Writer b。合在一起，就得到一个接受 Writer a 并返回 Writer b 的函数，这正是 fmap 应该产生的东西。

注意，这个论证非常一般：可以把 Writer 替换成任意类型构造器。只要它支持鱼运算符和 return，也就可以定义 fmap。所以 Kleisli 范畴中的修饰总是一个函子。（不过，并不是每个函子都能产生 Kleisli 范畴。）

你也许会想，我们刚定义的这个 fmap，是否与编译器通过 deriving Functor 为我们推导出来的 fmap 相同。有趣的是，确实相同。这源于 Haskell 实现多态函数的方式，称为参数多态（parametric polymorphism），它会产生所谓的“免费定理”。其中一个定理说，如果对某个类型构造器存在一个保持恒等的 fmap 实现，那么它必然是唯一的。

8.6 协变函子与逆变函子（Covariant and Contravariant Functors）

现在已经回顾过 writer 函子，让我们回到 reader 函子。它基于部分应用的函数箭头类型构造器：

(->) r

// with Kind Projector plugin
Function1[R, ?] or R => ?

可以把它改写为类型同义词：

type Reader r a = r -> a

type Reader[R, A] = R => A

如前所见，它的 Functor 实例如下：

instance Functor (Reader r) where
    fmap f g = f . g

implicit def readerFunctor[R] = new Functor[Reader[R, ?]] {
  def fmap[A, B](f: A => B)(g: Reader[R, A]): Reader[R, B] =
    f compose g
}

但就像 pair 类型构造器或 Either 类型构造器一样，函数类型构造器接受两个类型参数。pair 和 Either 在两个参数上都是函子性的，也就是双函子。函数构造器也是双函子吗？

尝试让它在第一个参数上具有函子性。先写一个类型同义词，它就像 Reader，只是把参数顺序翻过来：

type Op r a = a -> r

type Op[R, A] = A => R

这一次，我们固定返回类型 r，改变参数类型 a。看看能否匹配类型以实现 fmap，它应具有如下类型签名：

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

def fmap[A, B]: (A => B) => (A => R) => (B => R)

只有两个接受 a 并分别返回 b 和 r 的函数，根本没有办法构造出一个接受 b 并返回 r 的函数！如果能以某种方式反转第一个函数，让它接受 b 并返回 a，情况就不同了。我们不能反转任意函数，但可以走到反范畴中。

简短回顾一下：对每个范畴 $C$，都有一个对偶范畴 C^op。它与 $C$ 拥有相同对象，但所有箭头方向相反。考虑一个从 C^op 到某个范畴 $D$ 的函子：

F :: C^op -> D

这样的函子会把 C^op 中的态射 f^op :: a -> b 映射到 $D$ 中的态射 F f^op :: F a -> F b。但态射 f^op 暗中对应原范畴 $C$ 中的某个态射 f :: b -> a。注意方向被反转了。

现在，$F$ 是一个普通函子，但基于 $F$ 还可以定义另一个映射，它不是函子，暂且称为 $G$。它是从 $C$ 到 $D$ 的映射。它在对象上的映射方式与 $F$ 相同，但在映射态射时会反转方向。它接受 $C$ 中的态射 f :: b -> a，先把它映射为相反态射 f^op :: a -> b，然后把函子 $F$ 应用到它上面，得到 F f^op :: F a -> F b。

考虑到 F a 与 G a 相同，F b 与 G b 相同，整个旅程可以描述为：

G f :: (b -> a) -> (G a -> G b)

这是一种“带扭转的函子”。以这种方式反转态射方向的范畴映射称为逆变函子（contravariant functor）。注意，逆变函子只是来自反范畴的普通函子。顺便说一句，我们迄今研究的普通函子称为协变函子（covariant functor）。

下面是在 Haskell 中定义逆变函子（准确地说，逆变自函子）的类型类：

class Contravariant f where
    contramap :: (b -> a) -> (f a -> f b)

trait Contravariant[F[_]] {
  def contramap[A, B](f: B => A)(fa: F[A]): F[B]
}

我们的类型构造器 Op 是它的一个实例：

instance Contravariant (Op r) where
    -- (b -> a) -> Op r a -> Op r b
    contramap f g = g . f

implicit def opContravariant[R] = new Contravariant[Op[R, ?]] {
  def contramap[A, B](f: B => A)(g: Op[R, A]): Op[R, B] =
    g compose f
}

注意，函数 f 会把自己插入到 Op 的内容，也就是函数 g 的前面（也就是右边）。

如果注意到 Op 的 contramap 只是把参数翻转后的函数组合运算符，那么定义可以更简洁。有一个专门用来翻转参数的函数，叫作 flip：

flip :: (a -> b -> c) -> (b -> a -> c)
flip f y x = f x y

def flip[A, B, C]: (A => B => C) => (B => A => C) =
  f => y => x => f(x)(y)

借助它，可以得到：

contramap = flip (.)

def compose[A, B, C]: (A => B) => (C => A) => C => B =
  f => g => c => f(g(c))

def contramap[A, B, R](f: B => A)(g: Op[R, A]): Op[R, B] =
  flip(compose[A, R, B])(f)(g)

// or just: (f andThen g)

8.7 Profunctor

我们已经看到，函数箭头运算符在第一个参数上逆变，在第二个参数上协变。这种东西有名字吗？事实证明，如果目标范畴是 $Set$，这种东西称为 profunctor。由于逆变函子等价于来自反范畴的协变函子，profunctor 定义为：

C^op x D -> Set

由于在第一近似下，Haskell 类型就是集合，我们把 Profunctor 这个名字应用到一个双参数类型构造器 p 上，它在第一个参数上逆函子性，在第二个参数上函子性。下面是取自 Data.Profunctor 库的相应类型类：

class Profunctor p where
    dimap :: (a -> b) -> (c -> d) -> p b c -> p a d
    dimap f g = lmap f . rmap g

    lmap :: (a -> b) -> p b c -> p a c
    lmap f = dimap f id

    rmap :: (b -> c) -> p a b -> p a c
    rmap = dimap id

trait Profunctor[F[_, _]] {
  def bimap[A, B, C, D]: (A => B) => (C => D) => F[B, C] => F[A, D] =
    f => g => lmap(f) compose rmap[B, C, D](g)

  def lmap[A, B, C]: (A => B) => F[B, C] => F[A, C] =
    f => bimap(f)(identity[C])

  def rmap[A, B, C]: (B => C) => F[A, B] => F[A, C] =
    bimap[A, A, B, C](identity[A])
}

这三个函数都有默认实现。就像 Bifunctor 一样，声明 Profunctor 实例时，可以选择实现 dimap 并接受 lmap 和 rmap 的默认实现；也可以实现 lmap 与 rmap，接受 dimap 的默认实现。

现在可以断言，函数箭头运算符是 Profunctor 的实例：

instance Profunctor (->) where
    dimap ab cd bc = cd . bc . ab
    lmap = flip (.)
    rmap = (.)

implicit val function1Profunctor = new Profunctor[Function1] {
  override def bimap[A, B, C, D]: (A => B) => (C => D) => (B => C) => (A => D) =
    ab => cd => bc => cd compose bc compose ab

  override def lmap[A, B, C]: (A => B) => (B => C) => (A => C) =
    flip(compose)

  override def rmap[A, B, C]: (B => C) => (A => B) => (A => C) =
    compose
}

Profunctor 在 Haskell 的 lens 库中有应用。讨论端与余端时，我们还会再见到它们。

8.8 Hom 函子（The Hom-Functor）

上面的例子反映了一个更一般的陈述：把一对对象 $a$ 和 $b$ 映射为它们之间的态射集合，也就是 hom-set C(a, b) 的映射，是一个函子。它是从乘积范畴 C^op x C 到集合范畴 $Set$ 的函子。

定义它在态射上的作用。C^op x C 中的态射是一对来自 $C$ 的态射：

f :: a' -> a
g :: b -> b'

对这一对态射的提升，必须是从集合 C(a, b) 到集合 C(a', b') 的态射（也就是函数）。只要任选 C(a, b) 的元素 h（它是从 a 到 b 的态射），并把它映射为：

g . h . f

这就是 C(a', b') 的一个元素。

可以看到，hom 函子是 profunctor 的一个特例。

8.9 挑战（Challenges）

1. 说明下面的数据类型是双函子：

data Pair a b = Pair a b

额外加分：实现 Bifunctor 的全部三个方法，并使用等式推理说明，只要默认实现可以应用，这些定义就与默认实现兼容。

2. 说明标准 Maybe 定义与下面这个脱糖版本之间的同构：

type Maybe' a = Either (Const () a) (Identity a)

提示：定义两个实现之间的双向映射。额外加分：用等式推理说明它们互为逆。

3. 再尝试另一个数据结构。我把它称为 PreList，因为它是 List 的前身。它用类型参数 b 替代递归。

data PreList a b = Nil | Cons a b

可以通过把 PreList 递归应用到自身来恢复前面定义的 List（讨论不动点时会看到如何做到）。说明 PreList 是 Bifunctor 的实例。

4. 说明下面这些数据类型在 a 和 b 上定义了双函子：

data K2 c a b = K2 c
data Fst a b = Fst a
data Snd a b = Snd b

额外加分：把你的解答与 Conor McBride 的论文 Clowns to the Left of me, Jokers to the Right 对照检查。

5. 用 Haskell 以外的语言定义一个双函子。为该语言中的泛型 pair 实现 bimap。
6. std::map 在两个模板参数 Key 和 T 上应该被看作双函子还是 profunctor？你会如何重新设计这个数据类型，使其成为双函子或 profunctor？

参考资料

1. Conor McBride, Clowns to the Left of me, Jokers to the Right.