Monad

函数式编程 · qianyan · 于 发布 · 1080 次阅读
889

Monad不就是个自函子范畴上的幺半群,这有什么难理解的(A monad is just a monoid in the category of endofunctors)
—— Phillip Wadler

自函子(Endofunctor)

什么是函数(Function)?
函数表达的映射关系在类型上体现在特定类型(proper type)之间的映射。

什么是自函数(Endofunction)?

identity :: Number -> Number

自函数就是把类型映射到自身类型。函数identity是一个自函数的特例,它接收什么参数就返回什么参数,所以入参和返回值不仅类型一致,而且值也相同。

接下来,回答什么是自函子(Endofunctor)之前,我们先弄清什么是函子(Functor)?

函子有别于函数,函数描述的是特定类型(proper type)之间的映射,而函子描述的是范畴(category)之间的映射。

那什么是范畴(category)?

我们把范畴看做一组类型及其关系态射(morphism)的集合。包括特定类型及其态射,比如Int、String、Int -> String;高阶类型及其态射,比如List[Int]、List[String]、List[Int] -> List[String]

接下来看看函子是如何映射两个范畴的,见下图:
范畴

图中范畴C1和范畴C2之间有映射关系,C1中Int映射到C2中的List[Int],C1中String映射到C2中的List[String]。除此之外,C1中的关系态射Int -> String也映射到C2中的关系List[Int] -> List[String]态射上。

换句话说,如果一个范畴内部的所有元素可以映射为另一个范畴的元素,且元素间的关系也可以映射为另一个范畴元素间关系,则认为这两个范畴之间存在映射。所谓函子就是表示两个范畴的映射。

澄清了函子的含义,那么如何在程序中表达它?

在Haskell中,函子是在其上可以map over的东西。稍微有一点函数式编程经验,一定会想到数组(Array)或者列表(List),确实如此。不过,在我们的例子中,List并不是一个具体的类型,而是一个类型构造子。举个例子,构造List[Int],也就是把Int提升到List[Int],记作Int -> List[Int]。这表达了一个范畴的元素可以映射为另一个范畴的元素。

List具有map方法,不妨看看map的定义:

f :: A -> B
map :: f -> List[A] -> List[B]

具体到我们的例子当中,就有:

f :: Int -> String
map :: f -> List[Int] -> List[String]

展开来看:

map :: Int -> String -> List[Int] -> List[String]

map的定义清晰地告诉我们:Int -> String这种关系可以映射为List[Int] -> List[String]这种关系。这就表达了元素间的关系也可以映射为另一个范畴元素间关系。

所以类型构造器List[T]就是一个函子。

理解了函子的概念,接着继续探究什么是自函子。我们已经知道自函数就是把类型映射到自身类型,那么自函子就是把范畴映射到自身范畴。

自函子是如何映射范畴的,见下图:
Identity自函子范畴

图中表示的是一个将范畴映射到自身的自函子,而且还是一个特殊的Identity自函子。为什么这么说?从函子的定义出发,我们考察这个自函子,始终有List[Int] -> List[Int]以及List[Int] -> List[String] -> List[Int] -> List[String]这两种映射。
我们表述成:

类型List[Int]映射到自己
态射f :: List[Int] -> List[String]映射到自己

我们记作:

F(List[Int]) = List[Int]
F(f) = f
其中,F是Functor.

除了Identity的自函子,还有其它的自函子,见下图:
自函子范畴

图中的省略号代表这些范畴可以无限地延伸下去。我们在这个大范畴所做的所有映射操作都是同一范畴内的映射,自然这样的范畴就是一个自函子的范畴。

我们记作:

List[Int] -> List[List[Int]]
List[Int] -> List[String] -> List[List[Int]] -> List[List[String]]
...

所以List[Int]、List[List[Int]]、...、List[List[List[...]]]及其之间的态射是一个自函子的范畴。


幺半群

[幺半群][1]是一个带有二元运算 : M × M → M 的集合 M ,其符合下列公理:
结合律:对任何在 M 内的a、b、c, (a*b)*c = a
(b*c) 。
单位元:存在一在 M 内的元素e,使得任一于 M 内的 a 都会符合 a*e = e*a = a 。

接着我们看看在自函子的范畴上,怎么结合幺半群的定义得出Monad的。

假设我们有个cube函数,它的功能就是计算每个数的3次方,函数签名如下:

cube :: Number -> Number

现在我们想在其返回值上添加一些调试信息,所以返回一个元组(Tuple),第二个元素代表调试信息。函数签名如下:

f :: Number -> (Number,String)

结合前面所讲,我们很容易知道元组构造子(Number,String)是一个自函子。Number所在的范畴并不同于元组(Number,String)所在的范畴。换句话说,f的入参和返回值属于两个范畴。那么这会产生什么影响?我们看看幺半群的定义中规定的结合律。对于函数而言,结合律就是将函数以各种结合方式嵌套起来调用。我们将常用的compose函数看作此处的二元运算。

var compose = function(f, g) {
  return function(x) {
    return f(g(x));
  };
};

compose(f, f)

从函数签名可以很容易看出,右边的f运算的结果是元组,而左侧的f却是接收一个Number类型的函数,它们是彼此不兼容的。

有什么好办法能消除这种不兼容性?假如输入和输出都是元组,结果会如何呢?

F :: (Number,String) -> (Number,String)

compose(F, F)                 

这样是可行的!在验证满足结合律之前,我们引入一个bind函数来辅助将f提升成F.

f :: Number -> (Number,String) => F :: (Number,String) -> (Number,String)

var bind = function(f) {
  return function F(tuple) {
    var x  = tuple[0],
        s  = tuple[1],
        fx = f(x),
        y  = fx[0],
        t  = fx[1];

    return [y, s + t];
  };
};

我们来实现元组自函子范畴上的结合律:

var cube = function(x) {
  return [x * x * x, 'cube was called.'];
};

var sine = function(x) {
  return [Math.sin(x), 'sine was called.'];
};

var f = compose(compose(bind(sine), bind(cube)), bind(cube));
f([3, ''])

var f1 = compose(bind(sine), compose(bind(cube), bind(cube)));
f1([3,''])
>>>
[0.956, 'cube was called.cube was called.sine was called.']
[0.956, 'cube was called.cube was called.sine was called.']

这里f和f1代表的调用顺序产生同样的结果,说明元组自函子范畴满足结合律。

那如何找到这样一个e,使得a*e=e*a=a

// unit :: Number -> (Number,String)
var unit = function(x) { return [x, ''] };

var f = compose(bind(sine), bind(cube));

compose(f, bind(unit)) = compose(bind(unit), f) = f

这里的bind(unit)就是e了。

Monads for functional programming一书中介绍说monad是一个三元组(M, unit, *),对应此处就是(Tuple, unit, bind).

参考链接:
1. Translation from Haskell to JavaScript of selected portions of the best introduction to monads I've ever read
2. 我所理解的monad
3. Monads for functional programming


「软件匠艺社区」旨在传播匠艺精神,通过分享好的「工作方式」和「习惯」以帮助程序员更加快乐高效地编程。
本帖已被设为精华帖!
暂无回复。
需要 登录 后回复方可回复, 如果你还没有账号你可以 注册 一个帐号。