函数式编程中的单子(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等等。
领取专属 10元无门槛券
私享最新 技术干货