文章/答案/技术大牛

发布

社区首页 >专栏 >什么是 Monad (Functional Programming)？函子到底是什么?ApplicativeMonad

什么是 Monad (Functional Programming)？函子到底是什么?ApplicativeMonad

一个会写诗的程序员

发布于 2018-12-12 06:33:24

4.7K00

代码可运行

文章被收录于专栏：一个会写诗的程序员的博客一个会写诗的程序员的博客

运行总次数：0

代码可运行

什么是 Monad (Functional Programming)？

道生一，一生二，二生三，三生万物。

这里的“生”，就是 “apply 函数 ”（请注意，这里的 apply 动词）。
道，就是 X，一、二、三、万物等就是 Y。当然，这里的“一、二、三、万物” 都是函数。
“从无开始编程” 。

函数式编程的精髓就在于，我们可以用好多好多小小函数，搭搭搭，组成一个个大函数，最终写出整个程序来。比如我们想写一个函数

h: A -> C

然后手头有两个子函数：

f: A -> B
g: B -> C

于是我们用一个胶水函数

fun compose(f,g): A->C{
    return {x->g(f(x))}
}

把那两个小函数胶起来，做成我们要的 h 。

问题：f和g合并成了h，那么可以合并的函数需要符合什么条件呢？

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

Monad工作原理包含两个部分：对原范畴组合成新的范畴，这个范畴对于Monad来说必须是幺半群Monoid，可以认为Monad是一系列自函子的组合，这种组合是一种转换，转换的结果是Monoid。

Monad有以下特征：

Monad是一种定义将函数(函子)组合起来的结构方式。

这些组合的方法都是符合结合律的。

而Monoid是元素对象的组合的范畴，如果这种元素对象是函数或函子(也可能是Pipe，这就复杂了去了 )，那么Monad是自函子的组合范畴，Monad也是一种特殊的Monoid子集。

有一个特殊幺元，能够和任何元素组合，导致的结果是不改变这些元素。

函子到底是什么?

一个函子Functor是任意类型，这些类型定义了如何应用 map (fmap in Haskell) 。也就是说，如果我们要将普通函数应用到一个有盒子上下文包裹的值，那么我们首先需要定义一个叫Functor的数据类型，在这个数据类型中需要定义如何使用map或fmap来应用这个普通函数。这个函子Functor如下图：

image.png

fmap的输入参数是a->b函数，在我们这个案例中是(+3)，然后定义一个函子Functor，这里是Haskell的Just 2，最后返回一个新的函子，在我们案例中，使用Haskell是Just 5。下图展示了函子内部工作原理(多了一层上下文的“盒子”封装):

image.png

第一步是将值从上下文盒子中解救出来，然后将外部指定的函数(+3)应用到这个值上，得到一个新的值(5)，再将这个新值放入到上下文盒子中。是不是很形象生动？

Applicative

当我们的值被一个上下文包裹，就像函子Functor:

image.png

之前我们讨论的是如何将一个普通函数应用到这个函子中，现在如果这个普通函数也是一个被上下文包裹的：就叫 Applicative。它能知道如何应用一个被上下文包裹的函数到一个被上下文包裹的值中。

image.png

Monad

函子funtor是将一个普通函数应用到包裹的值:

image.png

Applicative应用一个包裹的函数到一个包裹的值:

image.png

Monad 则是将一个会返回包裹值的函数应用到一个被包裹的值上。

image.png

image.png

image.png

那么函子、applicative和Monad三个区别是什么？

image.png

functor: 应用一个函数到包裹的值，使用fmap/map.
applicative: 应用一个包裹的函数到包裹的值。
monad: 应用一个返回包裹值的函数到一个包裹的值。

面对对象（OOP）可以理解为是对数据的抽象，比如把一个人抽象成一个Object，关注的是数据。函数式编程是一种过程抽象的思维，就是对当前的动作去进行抽象，关注的是动作。

image.png

名词+动词= 图灵机 + 函数式 =对象(状态) + process

自函子(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]。

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

image.png

图中范畴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]就是一个函子。

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

自函子是如何映射范畴的，见下图：

image.png

图中表示的是一个将范畴映射到自身的自函子，而且还是一个特殊的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的自函子，还有其它的自函子，见下图：

[图片上传失败...(image-db344c-1542218165324)]

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

我们记作：

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， (ab)c = a(bc) 。 单位元：存在一在 M 内的元素e，使得任一于 M 内的 a 都会符合 ae = e*a = a 。

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

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

cube :: Number -> Number

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

f :: Number -> (Number,String)

入参和出参不一致，这会产生什么影响？我们看看幺半群的定义中规定的结合律。对于函数而言，结合律就是将函数以各种结合方式嵌套起来调用。我们将常用的compose函数看作此处的二元运算。

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

compose(f, f)

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

有什么好办法能消除这种不兼容性？结合前面所讲，cube是一个自函数Number -> Number，而元组(Number,String)在Hask范畴是一个自函子，理由如下：

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

假如输入和输出都是元组，结果会如何呢？

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

compose(fn, fn)

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

f :: Number -> (Number,String) => fn :: (Number,String) -> (Number,String)
注: 在Haskell中称为 liftM
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，此处的*是compose运算

// 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了。

到这里，思路逐步清晰了。在Haskell这类的强类型语言中，我们甚至可以组装自己的Tuple Monad。如下：

type Tuple(Number,String)
flatmap :: Tuple -> Number -> Tuple -> Tuple
unit :: Number -> Tuple
map :: Tuple >>= unit
    :: Tuple -> Number -> Number -> Tuple

//compose
// flatmap 即 bind，中缀表达式一般是 >>=
Tuple >>= (Number -> Tuple) >>= (Number -> Tuple)