竟然要写(2)了。

 

在说monad之前，先要讲讲functor。functor包括了两个变换，一个是同一个结构（集合）里的变换，比如f:a->b，另外一个是从一个结构到另一个结构的变换，比如a -> m a。functor的意思是，把一个结构的变换，提升到另一个结构里实现。整型的list是一个简单的functor，它可以把一个关于整型的变换，比如f x = x + 1 (这是一个累赘的写法，实际上 f = (+1)就可以了），提升上去。具体的行为就跟map类似。它的名字一般叫fmap，也就是说fmap有两个参数，第一个是a->b的映射，第二个是m a，也就是从a结构到 m a这个结构。

 

monad首先是一个functor。它的提升函数名字叫lift。也就是说lift类似于fmap。而每个monad都是从某个类型而来（m a里面的a）。monad至少要有两个函数：return（或者叫unit），>>= （或者叫bind）。return需要一个a类型的参数，返回一个m a类型的结果，unit这个名字表明了它实际上就是把一个a带进去monad里面。而bind是monad里最重要的函数。bind取两个参数，一个是m a，即当前的monad，另一个是a->m b，表示一个函数，这个函数根据某个a类型的输入可以得到一个m b类型的结果。bind的作用，简单来说就是从当前的monad获得的a生成一个新的monad： m b。

 

functional programming里面有一个很好的特性是组合性。两个函数可以很容易组合成一个新的函数，而在imperative的编程语言里，尤其在有全局变量和有各种锁的时候。但是functional的组合有个问题就是不容易实现imperative里面的控制逻辑，尤其在有laziness的时候。这种控制的逻辑有时候是必须的，比如说有effect的时候，一个例子是需要在console打印一些东西，打印的顺序是需要保留的。monad就是提供了一种机制来做这个事情。前面说了，bind首先会对一个m a求值，然后把结果交给第二个参数，然后得到一个m b。这里m a和m b都可以认为是一个计算，或者说，只有当求值的时候才真正执行。而bind的定义可以保证第一个计算会被先执行。这就获得sequential的性质了。

 

事实上，在>>=的基础上，可以有一个>>的函数。这个函数的定义就是 m a >> m b = m a >>= \ _ -> m b。也就是说忽略之前的输入，这就跟imperative的顺序执行基本一样了。需要注意的是，这些运算都是在m a这个结构上执行的。而不是在简单的a上。需要说明的是，前面的并不是真正的haskell code...

 

有了monad我们就可以很容易的引入错误处理了。以Maybe类型为例，它是一个简单的monad，有两种值，Just a表示正常的值a，而Nothing表示错误的值。这样，我们可以定义return a = Just a; Just a >>= f = f a; Nothing >>= f = Nothing。注意第三个式子，实际上把Nothing看作错误值就可以看到错误的传播。考虑有多个>>=组合的情况，如果对应到原有的f (Just a) = xxx; f Nothing = Nothing这样的繁复的写，monad的作法要简洁的多。

 

简单来说，monad就是一个自娱自乐的东西。主要是提供functional里面缺乏的imperative的一些特征。不会haskell基本听不懂，会了haskell基本不用说。完毕。。 

 

好像还没有写过跟计算机相关的东西。。

 

最近一段时间看了些functional programming的东西，稍微学了一点点haskell (haskell.org)。python也有一点点functional的东西，比如list comprehension, higher order function（map, filter, reduce这几个），不过python是一个很好用的语言，而haskell是一个相当难用的语言，主要的差别就是haskell的static type和pure fuctional。换一种比python更functional的语言，比如说erlang (www.erlang.org)，因为动态的类型和不那么pure，就好用的多。

 

回到functional，跟普通的imperative的语言，比如c/c++的，有什么好处呢？我觉得一个很大的好处就是没有了左值。左值实在是一切罪恶之源。。。没有了左值差不多就等于没有了全局变量，这将是多么美好的世界。在并发的时代，要保证正确的时序读写变量，当天才们的带各种锁的代码组合在一起的时候，实在很难才可以不崩溃。还有另一个好处，就是表达的更直接，比如说，对一个列表里的每个整型的元素加一，在haskell里，可以这么写：f l = map (+1) l. haskell的函数里，参数并不用括号，所以f l其实类似于python的f(l). l就是那个list，这种直接的表达方式会让编译器更容易优化。当然C++除了暴力写法，也有std::for_each。

 

functional programming还有些比较有意思的东西。比如函数作为first class citizen，closure，haskell还支持lazy evaluation。此外，还有一个稍微麻烦点的东西，continuation。但是这些，都不是functional programming的精华。functional programming的精华是monad。当然这句话不是我说的，我只是表示赞同而已。

 

关于continuation，其实跟closure关系也很大。举个简单的例子，阶乘：

递归写法：

fac 0 = 1

fac n = n * (fac (n-1))

 

高阶函数：

fact' n = foldl1 (*) [1..n]

fold就是类似于python的reduce.

 

continuation：

fact'' 0 k = k 1

fact'' n k = fact'' (n-1) (\x-> k (n * x))

continuation就是传递一个函数作为下一步要做的事情，比如上面的k，所以要把结果输出来，需要提供一个函数，一般就是id  (id x = x)。这样上面的意思是，当传入0的时候，下一个函数把1作为输入，当传入n的时候，则可以把一部分计算转移到下一个函数里，形成一个closure。大致就是要算n的阶乘，可以先算(n-1)的阶乘，然后把结果传递给下一个函数的时候，下一个函数应该先对输入乘以n。

 

当然这个也不算精华。只是一些新的思维方式而已。回到monad上来，monad是category理论的概念，category是很抽象的东西，据说category里面最多的不是定理，而是定义。functional programming除去效率低下（内存都不知道在哪里，别说操控了）以外，也有很明显的问题：imperative语言里面很简单的控制逻辑，包括执行的顺序，以及执行中的side effect，在pure的functional 语言里，都不那么容易表示。另一个就是，状态的保存和使用，在c++里，就是一个全局变量，而在functional programming里，如果不对pure作妥协，做起来也不那么容易。对于控制逻辑，理论上来说，用if-then-else都可以实现，只不过代码会膨胀的很厉害，且很难组合。当要支持很深层次的跳出，比如error handling和exception的处理等等，就只好再次崩溃了。先从顺序求值的需求说起，imperative的语言一行一行的写就可以了，肯定是按照顺序执行的，erlang的顺序求值通过逗号来完成，而对于支持laziness的haskell，就没那么简单了，每个表达式的求值都是当需要使用的时候才执行。monad是一个很漂亮的解决这个问题的方法。

 

有空再写。。

 

今天我跟蒋爷汇报了我们跪拜的事情。安酒神说，他努力一辈子也不能给蒋爷提鞋。

 

蒋爷沉吟半刻，很严肃的做了批示：

 

 

另，蒋爷说他的经历是一个best practice，而不仅仅是一个好的story或者一个reference case。

 

另2，我觉得下饭馆的时候，没有什么人是吃一个菜就买单的。

 

另3，昨天听一个哲学家聊天，这个世界上传统的中国人民，以及伟大的阿拉伯教众，加起来应该超过地球人口的一半。地球上有一半以上的人口都支持三妻四妾，这是多么神奇且伟大的事情！

 

在地球的另一边，蒋爷给他的理论找到了实证。可以看原文。

作为宇宙开端大爆炸的回音，我再感叹一下。