初识 monad

搞 functional programming 的人最终都会接触到 monad 这个概念,其实这是一个来自范畴论(后面有机会也来学习一些基本的概念,这个部分很早就听说了,但是却没看懂)的概念,虽然范畴论里面也有 monad 这样一个名词,但这里讲的却仅仅是其一个特殊情况,我们在后面看看究竟是啥关系。

在编程语言里面,monad 这样一个概念也被认为是 programmable semicolon,我们知道 imperative programming language 诸如 C/C++ 和 Java 通常以分号结束一个语句,你也可以将其看成将语句 chain 起来。所谓 programmable semicolon 就在这个意义上,通过 chaining expression 获得类似 pipeline 的行为,但是我们知道 imperative programming 里面的分号并没有能力将前后的语句真正 chaining 起来,这里是的确赋予了程序员这个能力。

形式上解释 monad 需要一个 type system,monad 其实是一种“construction”(代数结构),它在此 type system 建立一类特殊的类型(monadic type),那么结合某种语言如 scala 来说,scala 本身的 type system 里面我们通过某种方式建立一类类型(很显然常用的手段需要 generics),它需要以下三点要求(我们以 Option 这个 monad 为例):

  • type constructor,对应每一个 type system 的类型,对应的 monadic type 是啥,很简单的做法就是使用泛型表示,比如 Option[T] 就表示了一个 monad type constructor
  • unit 映射将 type system 某个 type 的对象映射成为 monadic type 里的成员,比如 val t: T,那么 Option 需要的就是一个将 t 映射成为 Option[T] 的函数
  • binding 是一个将给定的 monadic type 映射成为另一个同类的 monadic type 的函数,它还需要一个从前者的 type 到后者 type 对应的 monadic type 的映射函数,如果写成一个 pure function 这是一个两元函数,如果为 monadic type 本身提供“成员函数”,这就成为了一个一元的函数。仍然以 Option 为例,简言之我们需要一个 Option[T] 到 Option[U] 这样一个操作,操作需要一个参数 t: T => Option[U]。

有了这三个基本的东西之后,我们要求他们满足以下定律(是否觉得跟定义群、环之类的很像了?):

  • 结合率(associtivity):binding 满足结合率,如果记 m 为 monadic type M[T] 的实例,给定一个 f: T =>  M[U] 和 g: U => M[W],且 . 为 binding,(m . f) . g == m . (t: T => f(t) . g)
  • unit 映射满足 unit (t) . f = f(t) 与 m . unit = m,这也就是说 unit 映射类似一个单位元,任意类型的实例被其映射到 monadic type 里面的赋值映射,另一方面因为这个映射可以看成是 binding 的定义域里面一个,binding 对其操作后仍然回到原先的 monadic type 实例自身。如果把 binding 理解成为类似乘法的一个运算,unit 就是这个里面的 1

结合 Option 来说,满足以上条件的映射:

  • unit 映射是 t: T => Success (t)
  • binding 就是其对应的 flatMap

可以很容易的验证这几点。这告诉我们在 scala 里面普遍存在的这类操作并不是偶然,这类操作的存在使得我们可以 chaining 各种操作,除了容器类,前面还介绍了有 Try(尽管严格来说这并不是 monad)。实际上还有一类定义 monad 的方式,他们使用 fmap (将 T=>U 映射到 M[T] => M[U])和 join(类似 flatten),这里不再赘述。

那么 monad 这类结构除了以上 Option/Maybe、Collection 还能处理一些什么样的问题呢?

  • writer monad,为每步 function 调用附加一个 side effect,如记录 log,比如将 T 映射到 M[T] = Pair[T, String],做 flatMap 时 (f: T => M[U]) val (u, second) = f (first) ; (u, this.second + second)
  • identity monad,也就是 M[T] 还是 T
  • state monad,如果令 S 表示状态的类型,对应的 monad 类型为 M[T] = S => (T, S),即表示一个函数类型,将给定状态映射成为返回值 T 和下一个状态,这里的 unit 是 unit (t) = s: S => (t, s),做 flatMap 时相当于将实际计算放在 f 中,返回 f(t) 的是类似状态迁移的函数(如果计算给定,S => (g(t), S) 中 g(t) 给定),这样一个 monad 可以让程序员为计算过程附加任意一个状态类型,参看这里
  • environment monad 也称 reader monad,作用在于为计算提供一个共享的上下文环境,对应的 monad 类型为 M[T] = E => T,其中 E 是表示上下文的类型,对应的 unit (t) = e: E => t,ms 可以用来替换掉 IoC container 实现 DI,见这里
  • continuation monad 传说中实现 call/cc 的一个 monad,例子见这里

for comprehension 与 do notion

scala 里面提供了 for comprehension 本质上是对以上 monad 结构的应用,而这其实是广为 functional programming 人士所知的 do notation 的实现。通过 for 来操纵 monad 可以大大简化嵌套 flatMap 这类操作,这也很自然的将我原先 for 似乎就是类似对 iterable 做的 syntactic sugar 进行了纠正。不过上面提到的几种 monad 了解甚少,需要强化。

——————
And he said, What shall I give thee? And Jacob said, Thou shalt not give me any thing: if thou wilt do this thing for me, I will again feed and keep thy flock.

Advertisements
初识 monad

发表评论

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 / 更改 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s