Haskell 简介&示例

几个星期的上下班时间看完了 Learn You a Haskell。然后该 hack 点 code 了吧,本来想写个 Random Forest 的,后来看着难度高了点,于是准备从简单点的 Naive Bayes 开始。

这里先给个 Haskell 的示例兼简介。


上面的示例代码是用来计算 Monty Hall 问题 的,代码改写了 Probabilistic Functional Programming in Haskell 中的示例以适应 Haskell 2010 和新的 probability 库,执行的话需要先用 cabal 安装 probability 库

下面是逐行解释(行号需要点上面左下角的链接打开 gist 才能看到):

最开始只是些 module 的 import。

11行的 State 类型定义了问题的样本空间:放奖品的门的位置,选择的门的位置,被主持人打开的门的位置。
注意 deriving (Eq, Ord, Show, Read) 的代码,这就是 Haskell 的 type class,说明 State 这一类型可以判断是否相等(Eq),比较大小(Ord),并和字符串相互转换(Show / Read),这几个 type class 的实现因为很简单所以由系统代劳了。type class 一定程度上与 Java 的 interface,C++11 中被放弃的 concept,还有 Go 的 duck type 类似。

13行的 start 函数定义初始状态,:: 之前是函数名 start,之后是返回类型的 State。

16行、19行、22行定义了3个函数,分别是3个概率转移函数:确定奖品所在的门的位置,选择的门的位置,被主持人打开的门的位置。
Transition.T prob a 只是 a -> Distrubution.T prob a 的别名,也就是说,函数接受一个状态 State 为参数,返回一个概率分布 Distrubution.T Float State

17行的实现 [ ] 中的就是 list comprehension,从三个门中依次选择一个门,构造出 list 的三个元素(就是奖品在 A 门的 State,在 B 门的 State,在 C 门的 State)。然后 Distribution.uniform 将这个 list 转换成均匀分布的概率分布(奖品在任一扇门后的概率相等,均为三分之一)。

27和30行的 switch 函数和 stay 函数类似的定义了最后的决定,是交换之前的选择,还是维持。同样仍是概率转移函数。

33行的 game 函数把全过程串联起来。
其定义本身是高阶函数的例子,它的参数是 a -> Distrubution.T prob a 这一概率转移函数,返回的是把它作为最后一步的整个概率转移函数 a -> Distrubution.T prob a
另一方面,概率分布的类型 Distrubution.T prob a 则是 Haskell 中著名的 monad 类型。Monad 算是 Haskell 里比较难理解的概念了。简单来说,monad 是用于建模计算过程的一个通用模型,它可以套用在相当多的不同种类的计算过程中,因此 Haskell 直接给它准备了不少语法糖。比如在这里,monad 建模的就是概率分布和概率转移函数相关的计算,把概率转移函数应用在一个概率分布上生成另一个概率分布这一计算过程就被 probability 库实现在 monad 中了。

34行的实现就是对函数的 list 做了一次 reduce,利用 monad 的 Kleisli 组合将数个概率转移函数串联成一个概率转移函数。

38行的 result 函数将样本空间的样本点映射到胜或负的事件。

41行的 eval 函数将 game 函数最后得到的样本空间的样本点,按照 result 函数的定义,转换为概率模型的事件。

最后,在解释器中输入

eval switch

会得到

[(Lose,0.33333334),(Win,0.6666667)]

然后

eval stay

则得到

[(Win,0.33333334),(Lose,0.6666667)]

就是最后选择交换一个门的话会有翻倍的概率取胜。

没有在这个示例中得到体现的是 lazy evaluation 和 pattern matching。以后有机会再提吧。

Advertisements
This entry was posted in Computer and Internet, Programming and Algorithm and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s