范畴论 Kleisli范畴

您已经了解了如何将类型【types】和纯函数【 pure functions】建模为范畴。 我还提到范畴理论中有一种对副作用【 side effects】或非纯函数【non-pure functions】建模的方法。 让我们看一个这样的示例：记录或跟踪执行轨迹的函数。 在命令式语言中，我们可以通过改变某些全局状态，来实现该功能，例如：

string logger;bool negate(bool b) {logger += "Not so! ";return !b;}

你知道这不是一个纯函数，因为它的内存化【memoized】版本会错误的生成日志。该函数具有副作用【side effects】。

在现代编程中，我们尽量避免全局可变状态——如果只是因为并发的复杂性。你永远不会把这样的代码放到库中。

幸运的是，我们可以使这个函数变得纯粹。您只需显式地传入和传出日志即可。我们显式地添加一个字符串参数，并将常规输出与日志作为元组/序对【pair】返回：

pair<bool, string> negate(bool b, string logger) {return make_pair(!b, logger + "Not so! ");}

这个函数是纯粹的，他没有任何副作用，每次用相同的参数调用它时，它都返回相同的元组/序对【pair】，如果需要，它可以被内存化【memoized】。但是，考虑到日志的累积性，您必须记住所有可能调用的历史记录。比如会有这样的一个备忘条目：

negate(true, "It was the best of times. ");

以及

negate(true, "It was the worst of times. ");

等等。。

对于库函数【library function】来说，它也不是一个很好的接口。调用者可以忽略返回类型中的字符串，所以这不是一个很大的负担；但是他们被迫传递一个字符串作为输入，这可能不是很方便。

有没有一种方法能让重复做同样的事情变得不那么具有侵入性呢?有没有一种方法可以分离关注点呢？这个简单的示例中，negate函数的主要目的是将一个布尔值转换为另一个布尔值。 日志记录是次要的。 当然，被记录的消息是特定于该函数的，但是将该消息聚合到一个连续日志中的任务却是另一个问题。我们仍然希望函数生成一个字符串，但希望将它从产生日志的负担中解脱出来。因此，这是折衷解决方案：

pair<bool, string> negate(bool b) {return make_pair(!b, "Not so! ");}

其思想是在函数调用之间进行日志聚合。

为了了解如何做到这一点，让我们转到一个稍微现实一点的例子。我们有这样一个函数，它将一个字符串中的小写字母转换为大小字母：

string toUpper(string s) {string result;int (*toupperp)(int) = &toupper; // toupper is overloadedtransform(begin(s), end(s), back_inserter(result), toupperp);return result;}

另一种方法是将一个字符串按照空白符作为边界，拆分成一个字符串向量：

vector<string> toWords(string s) {return words(s);}

实际工作是在辅助函数words中完成的：

vector<string> words(string s) {vector<string> result{""};for (auto i = begin(s); i != end(s); ++i){if (isspace(*i))result.push_back("");elseresult.back() += *i;}return result;}

我们希望修改toUpper和toWords函数，以便它们在常规返回值之上附加一个消息字符串。

我们将“修饰【embellish】”这些函数的返回值。让我们用一种通用的方式来做，首先定义一个模板Writer，它封装了一个序列/元组，其中第一个分量【component】是任意类型A值，第二个分量【component】是字符串：

template<class A>using Writer = pair<A, string>;

以下是经过修饰的函数:

Writer<string> toUpper(string s) {string result;int (*toupperp)(int) = &toupper;transform(begin(s), end(s), back_inserter(result), toupperp);return make_pair(result, "toUpper ");}Writer<vector<string>> toWords(string s) {return make_pair(words(s), "toWords ");}

我们希望将这两个函数组合成另一个修饰函数【embellished function】，该函数将字符串大写并将其拆分为单词，同时生成这些操作的日志。我们可以这样做:

Writer<vector<string>> process(string s) {auto p1 = toUpper(s);auto p2 = toWords(p1.first);return make_pair(p2.first, p1.second + p2.second);}

我们已经实现了我们的目标：日志的聚合不再是某个函数的关注点了。它们只负责产生特定于自己的消息，然后在外部连接到一个更大的日志当中去。

现在想象一下用这种风格编写的整个程序。这是重复的、容易出错的代码的噩梦。但我们是程序员。我们知道如何处理重复的代码：我们抽象它！然而，这不是简单的抽象——我们必须抽象函数组合本身。但是组合是范畴论的本质，所以在我们编写更多代码之前，让我们从范畴的角度来分析这个问题。

4.1 The Writer Category

通过对函数的返回类型进行修饰，以承载一些额外功能，这种想法被证明是非常有效的。 我们将看到更多的例子。 起点还是由类型【types】和函数【function】组成的常规范畴。 我们仍将类型【types】保留为对象，但重新定义态射为修饰函数【embellished function】。

例如，假设我们想要修饰函数isEven，它从int到bool。我们把它变成一个由修饰函数【embellished function】所表示的态射【morphism】。重要的一点是，这个态射【morphism】仍然被认为是int对象和bool对象之间的箭头，即使修饰函数【embellished function】返回的是元组/序对【pair】:

pair<bool, string> isEven(int n) {return make_pair(n % 2 == 0, "isEven ");}

根据范畴的法则，我们应该能够将这个态射与另一个从bool对象到任何对象的态射【morphism】组合起来。特别是，我们应该能够将它与我们先前定义的negate组合起来：

pair<bool, string> negate(bool b) {return make_pair(!b, "Not so! ");}

显然，由于输入/输出不匹配，我们不能像我们组合常规函数那样来组合这两个态射【morphisms】。他们的组合应该看起来更像这样：

pair<bool, string> isOdd(int n) {pair<bool, string> p1 = isEven(n);pair<bool, string> p2 = negate(p1.first);return make_pair(p2.first, p1.second + p2.second);}

因此，在我们正在构建的这个新范畴中，两个态射的组合的方法为：

执行对应于第一个态射的修饰函数提取元组/序对【pair】结果中的首个分量【component】，并将其传递给对应于第二个态射的修饰函数将第一个结果的第二个分量【component】(字符串)和第二个结果的第二个分量【component】(字符串)连结起来返回一个新的元组/序对【pair】,其中第一个分量【component】是最终结果，第二个分量【component】是连结后的字符串

如果我们想要在c++中将这个组合抽象为一个高阶函数，我们必须使用一个由三个类型参数化的模板，这三个类型对应于我们的范畴中的三个对象。它应该接受两个修饰函数，并返回第三个修饰函数：

template<class A, class B, class C>function<Writer<C>(A)> compose(function<Writer<B>(A)> m1,function<Writer<C>(B)> m2){return [m1, m2](A x) {auto p1 = m1(x);auto p2 = m2(p1.first);return make_pair(p2.first, p1.second + p2.second);};}

现在我们可以回到前面的例子，使用这个新模板实现toUpper和toWords的组合:

Writer<vector<string>> process(string s) {return compose<string, string, vector<string>>(toUpper, toWords)(s);}

可以看到，在向compose模板传递类型时仍然有很多杂音。这是可以避免的，只要你有一个兼容c++ 14的编译器，它支持带有返回类型推断的泛型lambda函数:

auto const compose = [](auto m1, auto m2) {return [m1, m2](auto x) {auto p1 = m1(x);auto p2 = m2(p1.first);return make_pair(p2.first, p1.second + p2.second);};};

在这个新定义中，process的实现被简化为:

Writer<vector<string>> process(string s) {return compose(toUpper, toWords)(s);}

但我们还没有结束。我们已经在我们的新范畴中定义了组合，但是恒等态射是什么呢?这些不是我们常规的恒等函数！它们必须是从A类型到A类型的态射，这意味着它们是如下形式的修饰函数：

Writer<A> identity(A);

它们需要在组合中表现得像单位元【unit】。如果你看一下我们的组合的定义，你会看到一个恒等态射应该透传传入的参数而不改变，并且只在日志中贡献一个空字符串：

template<class A> Writer<A> identity(A x) {return make_pair(x, "");}

你可以很容易地说服自己，我们刚刚定义的范畴确实是一个合法的范畴。特别地，我们的组合是满足可结合性的【associative】。如果你关注每个元组/序对【pair】中第一个分量【component】，它只是一个常规的函数组合，它是可结合的【associative】。第二个分量【component】是字符串连结，而这也是可结合的【associative】。

精明的读者可能会注意到，这种结构很容易推广到任何一个幺半群【Monoid】，而不仅仅是字符串幺半群【Monoid】。我们将在compose内部使用mappend，在identity内部使用empty(替换掉**+和""**)。确实没有理由将自己限制为仅记录字符串。一个好的库开发者应该能够识别使库工作的最小约束——再这里，日志记录库的唯一要求是日志具有monoidal性质。

4.2 Writer in Haskell

同样的事情在Haskell中要更简洁一些，而且编译器也提供了很多帮助。让我们从定义Writer类型开始：

type Writer a = (a, String)

type Writer[A] = (A, String)

这里我只是定义了一个类型别名，相当于c++中的typedef(或using)。类型Writer由类型变量a参数化，等价于a和String的元组/序对【pair】。元组/序对【pair】的语法很简洁：括号中由逗号分隔的两个条目。

我们的态射是那些从任意类型到某些Writer类型的函数：

a -> Writer b

A => Writer[B]

我们将该组合声明为一个有趣的中缀操作符，美名其曰“fish”：

(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)

def >=>[A, B, C](m1: A => Writer[B], m2: B => Writer[C]): A => Writer[C]

它是一个有两个参数的函数，每个参数都是一个函数，并返回一个函数。第一个参数的类型是(a -> Writer b)，第二个参数是(b -> Writer c)，结果是(a -> Writer c)。

下面是中缀运算符的定义——两个参数m1和m2分别出现在fishy符号的两侧：

m1 >=> m2 = \x ->let (y, s1) = m1 x(z, s2) = m2 yin (z, s1 ++ s2)

object kleisli {//allows us to use >=> as an infix operatorimplicit 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)}}}

结果是一个lambda函数，该函数只有一个参数x。lambda被写成反斜杠【backslash】—— 把它看作是截断了一条腿的希腊字母λ。

let表达式允许您声明辅助变量【 auxiliary variables】。这里，调用m1返回的结果被模式匹配【 pattern matched】为一个变量为(y, s1)的元组/序对【pair】;而调用m2返回的的结果被模式匹配为(z, s2)。

在Haskell中，使用模式匹配操作元组/序对【pair】是很常见的，而不需要像我们在c++中那样使用访问器【accessors】。除此之外，这两个实现之间有一个非常简单的对应关系。

let表达式的整体值【overall value】在它的in子句中指定：这里是一个元组/序对【pair】，它的第一个分量【component】是z，第二个分量【component】是两个字符串s1++s2的连结。

我还将为我们的范畴定义恒等态射【identity morphism】，但出于稍后会变得清楚的原因，我将其称为return。

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

def pure[A](x: A): Writer[A] = (x, "")

为了完整起见，让我们使用Haskell版本的修饰函数：

upCase :: String -> Writer StringupCase s = (map toUpper s, "upCase ")toWords :: String -> Writer [String]toWords s = (words s, "toWords ")

val upCase: String => Writer[String] =s => (s.toUpperCase, "upCase ")val toWords: String => Writer[List[String]] =s => (s.split(' ').toList, "toWords ")

其中，函数map对应于C++的transform，它将toUpper函数应用到字符串s上，而辅助函数words是定义早Hashell的标准Prelude包里的。

最后，在fish操作符的帮助下，我们完成了这两个函数的组合：

process :: String -> Writer [String]process = upCase >=> toWords

val process: String => Writer[List[String]] = {import kleisli._upCase >=> toWords}

4.3 Kleisli Categories

你可能已经猜到，我并没有当场发明这个范畴。这就是所谓的Kleisli范畴的一个例子 —— 一个基于单子【monad】的范畴。我们还没有准备好讨论单子【monad】，但我想让你们见识一下它们的能耐。出于我们有限的目的，Kleisli范畴将底层编程语言的类型视为对象。从类型𝐴到类型𝐵的态射，对应于从𝐴到从B经特殊修饰衍生出来的类型的函数。每个Kleisli范畴定义了自己的方式来组合这样的态射，以及关于该组合下的恒等态射。(稍后我们将看到，这个不精确的术语“修饰”，其实对应于范畴内的自函子【endofunctor】概念)

我在本文中用作范畴基础的特定单子【monad】称为writer monad，它用于记录或跟踪函数的执行情况。 这也是在纯计算中嵌入效果的一种通用的机制的例子。 您之前已经看到，我们可以在集合范畴中（通常不考虑底部）对编程语言中的类型【types】和函数【functions】进行建模。 在这里，我们已将该模型扩展到一个稍有不同的范畴，该范畴中的态射【morphisms 】由修饰函数【embellished functions】表示，它们的组合也不仅仅将一个函数的输出传递给另一个函数的输入。 我们又多了一个可以玩的自由度：组合【composition】本身。 事实证明，这正是自由度，使我们有可能给程序提供简单的指称语义，而在命令式语言中，这些程序传统上是使用副作用实现的。

4.4 Challenge

未为其参数的所有可能值定义的函数称为部分函数【partial functio】。 从数学意义上讲，它并不是真正的函数，因此不符合标准的范畴模型【categorical mold】。 但是，可以通过表示为返回一个Optional修饰类型的函数，来使其成为数学意义上的函数：

template<class A> class optional {bool _isValid;A _value;public:optional() : _isValid(false) {}optional(A v) : _isValid(true), _value(v) {}bool isValid() const {return _isValid; }A value() const {return _value; }};

例如，下面是经过修饰的safe_root函数的实现:

optional<double> safe_root(double x) {if (x >= 0) return optional<double>{sqrt(x)};else return optional<double>{};}

下面是挑战：

构造部分函数【partial functions】的Kleisli范畴(定义其组合和恒等态射)实现经过修饰的safe_reciprocal函数，如果入参不是0，那么它会返回参数的有效倒数将safe_root与safe_reciprocal组合，实现一个safe_root_reciproca函数，该函数会在可能的情况下计算sqrt(1/x)

如果觉得《范畴论 Kleisli范畴》对你有帮助，请点赞、收藏，并留下你的观点哦！