Haskell Monad（上）

函数式编程中的单子(Monad)

说到pure functional programming，实在是绕不过去Monad的。

pure function的特点

往往用函数式编程的思路写了几个程序之后就会遇到一个问题：针对具有状态更新的程序，似乎总是不太好处理。由于语言的纯粹性，相同的输入总是返回一样的值，所以如果在计算过程中需要更新一个状态，就要去显式地把状态作为参数传递给函数，并显式地构造递归去实现状态更新。这经常是一个繁琐的过程。

譬如（以一个求值器为例）：

1、错误处理：如果要在模块中加入错误处理，那么需要在每一次的递归中检查状态并进行处理。（命令式语言中通过异常实现）

2、计数：同样要修改每次的递归。（imperative language中通过全局变量就能搞定。）

3、trace：需要插入调试信息的时候也是需要显式的在递归中插入打印信息。（imperative language中打印就能解决。）

而monad正是解决上述问题的途径。

evaluator的Monad实现

1、evaluator定义

假设term定义如下

一个Term要么是整数，要么是两个Term的商。

一个简单的evaluator定义如下：

输入如下两个Term:

则eval结果：answer = 4, error = undefined

2、考虑错误处理的eval过程

通过构造新的返回值来支持Exception

3、添加状态处理

假设我们现在要记录除法的次数，在命令式语言（譬如C）中通过定义一个初值为0的全局变量，每次除法递增1就可以了。

在纯函数式环境中，定义如下类型

一个函数类型，输入初始状态，返回最终状态和计算值得组合对。

eval实现如下

每次做除法的时候都要传入状态st。

3、中间输出调试

类似于上面的思路，定义

表达式告诉我们，先对x求值，再对y求值。

4、单子化的求值器

从上面的例子可以看出输出类型的特点是具有M a这样的形式。事实上，我们把eval的类型从改写成了。

这就是monadic function的形式了。诸如状态、输出、异常等作用都通过M来实现。

现在思考一个问题：Monad需要哪些操作？

从evaluator的例子看出首先要有一个生成Monad的函数unit

其次从递归过程中看出需要一个函数a -> M b，来对M a进行操作

定义Monad：一个三元组(M, unit, ＊)，包括类型构造子M、两个多态化的操作。通过Monad实现的表达式通常有这样的形式：

m∗λa.n

λa.n

是一个lambda表达式，上式理解为执行操作m，把结果绑定到a，然后执行操作n。从类型推导的角度来理解这个表达式是这样的：m的类型是M a，变量a类型为a，表达式n类型为M b，lambda表达式

λa.n

类型为a -> M b，所以整个表达式的类型为M b。

用monad的思路重写eval:

上式等价于

通过monad，我们就能避免每次（譬如带state/output/exception）都要重写求值器。下面一一道来。

5、回到basic evaluator

这样的monad称为Identity monad，用该monad重写式2-2得到了和simple evaluator等价的求值器。

关于实际的样例代码在下篇中给出。

6、monad实现异常处理（exception monad）

重新定义Monad如下：

用这个monad替换2-5式中的Monad定义，然后把unit(a/b)改为

即可。这样展开的monadic function和式2-1是等价的。

7、state monad

unit a返回(a, x)，即结束状态等于初始状态。

通过这个monad来定义2-2式，并且使得unit(a/b)为

8、output monad

output monad中的unit返回空字符串和值a构成的对，调用(m＊k)先从提取输出x和a， 然后从k a提取y和b，最终返回x和y的拼接字符串和值b构成的对。out x返回输出字符串x和空值构成的对。

Monad法则

通过Monad的定义我们可以得出Monad类型类的以下三条法则。

1、左单元操作

2、右单元操作

3、结合律

从上式可以看出结合律并不是所有情况都能满足的，假如a作为一个自由变量出现在表达式o中，那么这个推导显然是不成立的。

好，关于Monad的上篇到此结束，下篇预告：

一、上篇中关于Monad案例给出具体代码，可在ghci中运行。

二、做一些更加深入的探讨，关于parser，关于list等等。