Kleisli Categories - Kleisli范畴

可以基于范畴论对副作用/非纯函数进行建模。

考虑一个跟踪程序，在命令式编程语言中，经常是以修改某些全局状态来实现，例如

1
2
3
4
5


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

通过修改全局变量logger，实现对于程序运行情况的跟踪。但是现代编程语言中，一般尽可能不去修改全局状态，尤其是并发编程这一复杂情景。我们可以考虑重构以上方法，使之变成一个纯函数

1
2
3


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

现在这是一个纯函数了，它没有副作用了，传入相同的参数即可得到完全相同的结果。但若是关心跟踪的详细情况，考虑到累积性，不得不收集这个函数运行情况的全部历史，每调用它一次，就产生一个结果。作为一个库函数，这是特别难用的。调用者可以随意丢掉返回值当中的字符串（若是他不关心跟踪的具体情况），可是还必须传入一个字符串参数，这用起来很不方便了。

考虑消除这些东西，将我们关心的东西分离出来。本例中，negate主要任务是将布尔值转换成另一个，至于记录运行情况，那是次要的。尽管日志信息对于这个函数而言是特定的，但是将信息汇集到一个连续的日志这一任务是可单独考虑的。我们依然想让这个函数生成日志信息，但是可以减轻一下它的负担。现在有一个折中的解决方案

1
2
3


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

这样，日志信息的汇集工作就被转移至函数的当前调用之后且在下一次被调用之前的时机。

现在给出一个更现实的示例，现有一个小写转大写（字符串到字符串）和字符串分割成单词（字符串到字符串向量）的函数

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


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

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

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

现在我们想将函数toUpper和toWords修改一下，让它们返回值肩负日志信息。

通过“修饰”两个函数的返回值，采用更泛化一些的方式，定义一个Writer模板先

1
2


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

然后修改两个函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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 ");
}

现在想将这两函数复合，得到一个先将字符串转大写，然后将之分割成单词的函数，此外也应当记下执行跟踪信息也不能丢失，所以这样实现

1
2
3
4
5


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

现在已经完成了目标：日志的汇集不再由单个的函数来操心。这些函数各自产生各自的消息，然后在外部汇总为一个更大的日志。

整个程序都这么写的话，那么会有特别多重复代码，解决方式便是进行抽象。但这不是普通的抽象，是在对函数的复合本身进行抽象。由于复合是范畴论的本质，因此在动手之前，我们先从范畴的角度分析一下这个问题。

The Writer Category

对那几个函数的返回类型进行“修饰”，其意图是为了让返回类型肩负着一些有用的附加功能。这一策略相当有用，下面将给出更多的示例。起点还是常规的的类型与函数的范畴。我们将类型作为对象，与以前有所不同的是，现在将装帧过的函数作为态射了。

假设我们要修饰从int到bool的isEven函数，然后将修饰后的函数作为态射，尽管修饰后的函数返回一个元组/序对，但我们依然认为它是个从int到bool的态射。

1
2
3


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

按照范畴中态射的复合法则，应当可以与我们之前定义的negate进行复合。

1
2
3


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

显然无法通过常规方式进行态射复合，因为输入输出不匹配，我们可以这样实现

1
2
3
4
5


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);
}

对这种新范畴中态射复合的法则进行总结：

执行与第一个态射所对应的装帧函数，得到第一个序对；
从第一个序对中取出第一个元素，将这个元素传给与第二态射对应的装帧函数，得到第二个序对；
将两个序对中的第二个元素（字符串）连接起来；
将计算结果与连接好的字符串捆绑起来作为序对返回。

若想将这种复合抽象为 C++ 中的高阶函数，必须根据与我们的范畴中的三个对象相对应的三种类型构造一个参数化模板。这个函数应该接受能遵守上述复合法则的两个可复合的装帧函数，返回第三个装帧函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

1
2
3


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

对于支持 C++14 的编译器，它支持具有返回类型推导功能的泛型匿名函数

1
2
3
4
5
6
7


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);
    };
};

用这个新的compose可以简化process

1
2
3


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

在这个新范畴里，我们已经定义了态射复合，但是还没有定义恒等态射。这些恒等态射肯定不是常规意义上的恒等态射！它们必须是一个从（装帧之前的）类型 A 到（装帧之后的）类型 A 的的态射，即：

1

Writer<A> identity(A);

对于复合而言，它们的行为必须像 unit。若要符合上面的态射复合的定义，那么这些恒等态射不应该修改传给它的参数，并且对于日志它们仅贡献一个空的字符串：

1
2
3
4


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

我们所定义的这个范畴是一个合法的范畴。特别是，我们所定义的态射的复合是遵守结合律的，虽然这无关紧要。如果你只关心每个序对的第一个元素，这种复合就是常规的函数复合。第二个元素会被连接起来，而字符串的连接也是遵守结合律的。

这种构造适用于任何幺半群，而不仅仅是字符串幺半群。我们可以在 compose 中使用 mappend，在 identify 中使用 mempty。

Writer in Haskell

同样的事情，在Haskell中做起来简单一些，而且也能得到编译器的很多辅助

首先定义Writer

1

type Writer a = (a, String)

声明复合操作符如下所示

1

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

其定义如下所示

1
2
3
4


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

1
2
3
4


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

恒等态射

1
2


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

上面几个例子，用Haskell演示其实现如下所示

1
2
3
4


toUpper :: String -> Writer String
toWords :: String -> Writer [String]

process = toUpper >=> toWords