单子,想弄不懂都很难

C 语言里没有现代程序员热衷于讨论的那些东西。

不过,那些东西不是原本就没有么?

下面我尝试用 C 语言来写一个单子(Monad)。

看下面这段代码:

typedef struct {
        void *thing;
} Maybe;

在 C 语言里,这是个结构体,而且是一个似乎很无聊的结构体。这种结构体能用来做什么呢?

可以作为函数的返回值类型。例如:

Maybe foo(void *thing)
{
        return (Maybe){.thing = thing};
}

假设 foo 像下面这样调用:

Maybe a = foo(thing); /* thing 指向前面出现的某个变量 */

那么,当 a.thingNULL 时,表示 foo 函数执行失败,否则表示执行成功。

那么 foo 函数的作用就将一种类型包装成 Maybe 类型。

NULL 可能会吓着一些对 C 语言原本就没怎么有好感的人,可以给它换个名字:

#define Nothing NULL

现在,可以认为当 a.thingNothing 时,表示 foo 函数执行失败,否则表示执行成功。

接下来,为 Maybe 类型定义这样的函数:

Maybe aha(void * (*f)(void *), Maybe a)
{
        return foo(f(a.thing));
}

这个函数可以将一个函数 f 作用于 a.thing。假设这个 f 为:

void *textize(void *thing)
{
        int *x = thing;
        char *text = malloc(32 * sizeof(char));
        sprintf(text, "%d", *x);
        return text;
}

有了像 textize 这样的函数,就可以用 aha 函数了,如下:

int a = 2;
Maybe x = aha(textize, foo(&a));

结果得到的 x.thing 会指向一个字符串 "2"

一个类型再加上一个针对这种类型的 aha 这样的函数,叫函子。

现在,再为 Maybe 类型构造一个函数:

Maybe bar(Maybe a, Maybe (*contuation)(void *thing))
{
        return a.thing ? contuation(a.thing) : (Maybe){.thing = Nothing};
}

现在,可以宣布有了一个 Maybe 单子。

这个 bar 函数有什么用呢,它能够按照顺序安全地组合一组形状相同的函数,从而起到一个函数的效果。例如,对于下面的三个函数:

Maybe test_a(void *thing)
{
        (*(int *)thing) *= 10;
}

Maybe test_b(void *thing)
{
        (*(int *)thing) *= 100;
}

Maybe test_c(void *thing)
{
        (*(int *)thing) += 1000;
}

使用 bar 可以把它们按照顺序装配起来:

int a = 2;
Maybe x = bar(bar(bar(foo(&a), test_a), test_b), test_c);

结果 x.thing 依然是指向变量 a 的指针,经过一组函数的处理,a 的值变成了 3000。

与上述代码等价的代码,也是 C 程序员惯用的代码如下:

int a = 2;
Maybe x = foo(&a);
if (x.thing) {
        x = test_a(x.thing);
        if (x.thing) {
                x = test_b(x.thing);
                if (x.thing) {
                        x = test_c(x.thing);
                }
        }
}

一个单子,由一种类型以及针对这种类型的类似 foobar 这样的函数构成。

上面我用的 fooaha 以及 bar 这些名字,有一些恶意的调侃。值得注意的是,aha 函数实际上可以基于 foobar 来定义。例如:

Maybe aha(void * (*f)(void *), Maybe a)
{
        return bar(foo(f(a.thing)), foo);
}

虽然稍微有点绕圈子,但是 aha 的确是基于 foobar 定义了出来。这说明了什么呢?

单子的层次高于函子。

倘若你能理解上述代码所体现出来的形式,那么上面出现的东西是叫对象、态射、函子、自函子、自然变换、自函子范畴、幺半群、单子,还是别的什么东西,很重要吗?我以为这些东西只是对研究数学的人很重要,而对于编程的人来说……只要你写的代码足够简约,足够具备复用性,那么就一点都不重要。

倘若觉得很重要,那么好吧,就掰扯一下,以问答的形式。

Q:什么是范畴?

A:范畴由对象和态射构成。例如,C 语言里的数据类型与函数。

Q:什么是函子?

A:函子可以将一种对象变成另一种对象,将一种态射变成另一种态射。例如,上面的 Maybe,将 void * 变成了 Maybe 类型;上面的 ahatextize 这种 void * -> void * 的函数变成了 Maybe -> Maybe 的函数。

Q:什么是自函子?

A:将一个范畴里的对象和态射变成这个范畴里的对象和态射的函子就是自函子。作家、画家、歌唱家、演员、舞者、政客、运动员……从事各种职业的人,都是自函子。什么职业都不从事的人也是自函子,他们就是 foo 函数。也有一些不是自函子的人,多数在精神病院里,还有一些在外面跳大神。

Q:什么是自函子范畴?

A:一个自函子构成的范畴。这个范畴里就一个东西,这个自函子。这个范畴里面的态射,叫自然变换。foobar 都是自然变换。

Q:什么是自函子范畴上的幺半群?

A:将自函子范畴里的所有态射视为集合,那个自函子就消失了。也就是说,自函子转化成了一个态射集合,这个集合叫 Hom-集。想一想自个,当你爱上一个人或什么东西的时候,你就消失了,我们管这个叫忘我。过去的人思慕成仙,要成仙,首先要忘我,然后去搞行为艺术。艺术是永恒的,对吧?这种行为艺术怎么搞呢?需要先搞一个幺元(也有很多人叫单位元)。这个幺元啊,就是眼观鼻、鼻观心、意守丹田。有了幺元,就可以驱动真气,打通任督二脉……做到这两步,就得到了幺半群。

Q:玄学?

A:计算机里运行的玄学。

文章来源:

Author:garfileo
link:https://segmentfault.com/a/1190000012435966