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等等。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180506G1F00H00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券