泛函编程(24)-泛函数据类型-Monad, monadic programming

    在上一节我们介绍了Monad。我们知道Monad是一个高度概括的抽象模型。好像创造Monad的目的是为了抽取各种数据类型的共性组件函数汇集成一套组件库从而避免重复编码。这些能对什么是Monad提供一个明确的答案吗?我们先从上节设计的Monad组件库中的一些基本函数来加深一点对Monad的了解:

 1   trait Monad[M[_]] extends Functor[M] {
 2       def unit[A](a: A): M[A]
 3       def flatMap[A,B](ma: M[A])(f: A => M[B]): M[B]
 4       def map[A,B](ma: M[A])(f: A => B): M[B] = {
 5           flatMap(ma){a => unit(f(a))}
 6       }
 7       def map2[A,B,C](ma: M[A], mb: M[B])(f: (A,B) => C): M[C] = {
 8           flatMap(ma) { a => map(mb){ b => f(a,b) }}
 9       }
10       def sequence[A](lm: List[M[A]]): M[List[A]] = {
11           lm.foldRight(unit(Nil: List[A])){(a,b) => map2(a,b){_ :: _} }
12       }
13       //递归方式sequence
14       def sequence_r[A](lm: List[M[A]]): M[List[A]] = {
15           lm match {
16               case Nil => unit(Nil: List[A])
17               case h::t => map2(h,sequence_r(t)){_ :: _}
18           }
19       }
20       //高效点的sequence(可以并行运算Par)
21       def bsequence[A](iseq: IndexedSeq[M[A]]): M[IndexedSeq[A]] = {
22           if (iseq.isEmpty) unit(Vector())
23           else if (iseq.length == 1) map(iseq.head){Vector(_)}
24           else {
25               val (l,r) = iseq.splitAt(iseq.length / 2)
26               map2(bsequence(l),bsequence(r)) {_ ++ _}
27           }
28       }
29       def traverse[A,B](la: List[A])(f: A => M[B]): M[List[B]] = {
30           la.foldRight(unit(Nil: List[B])){(a,b) => map2(f(a),b){_ :: _}}
31       }
32       def replicateM[A](n: Int, ma: M[A]): M[List[A]] = {
33           if (n == 0) unit(Nil)
34           else map2(ma,replicateM(n-1,ma)) {_ :: _}
35       }
36       def factor[A,B](ma: M[A], mb: M[B]): M[(A,B)] = {
37           map2(ma,mb){(a,b) => (a,b)}
38       }
39       def cofactor[A,B](e: Either[M[A],M[B]]): M[Either[A,B]] = {
40           e match {
41               case Right(b) => map(b){x => Right(x)}
42               case Left(a) => map(a){x => Left(x)}
43           }
44       }
45   }

我们分别用M[A]对应List[A],Option[A]及Par[A]来分析一下sequence函数的作用:

1. sequence >>> 用map2实现 >>> 用flatMap实现:

   对于List: sequence[A](lm: List[M[A]]): M[List[A]] >>> sequence[A](lm: List[List[A]]): List[List[A]] 

             >>> map2(list(list1),list(list2)){_ :: _} ,把封装在list里的list进行元素分拆交叉组合,

             例:(List(List(1,2),List(3,4)) >>> List[List[Int]] = List(List(1, 3), List(1, 4), List(2, 3), List(2, 4))

             sequence的作用体现在List.map2功能。而List.map2则是由List.flatMap实现的。所以sequence的行为还是依赖于List实例中flatMap的实 现方法

   对于Option: sequence[A](lm: List[M[A]]): M[List[A]] >>> sequence[A](lm: List[Option[A]]): List[Option[A]] 

             >>> map2(list(opton1),list(option2)){_ :: _} ,把封装在list里的元素option值串成list,

             例:(List(Some(1),Some(2),Some(3)) >>> Option[List[Int]] = Some(List(1, 2, 3))

             由于sequence的行为还是依赖于实例中flatMap的实现,Option 的特点:flatMap None = None 会产生如下效果:

             List(Some(1),None,Some(3)) >>> Option[List[Int]] = None

   对于Par: sequence[A](lm: List[M[A]]): M[M[A]] >>> sequence[A](lm: List[Par[A]]): List[Par[A]] 

             >>> map2(list(par1),list(par2)){_ :: _} ,运行封装在list里的并行运算并把结果串成list,

             这里Par.flatMap的功能是运行par,run(par)。这项功能恰恰是并行运算Par的核心行为。

从分析sequence不同的行为可以看出,Monad的确是一个通用概括的抽象模型。它就是一个很多数据类型组件库的软件接口:使用统一的函数名称来实现不同数据类型的不同功能效果。

  与前面讨论过的Monoid一样,Monad同样需要遵循一定的法则来规范作用、实现函数组合(composition)。Monad同样需要遵循结合性操作(associativity)及恒等(identity)。

Monoid的结合性操作是这样的:op(a,op(b,c)) == op(op(a,b),c)  对Monad来说,用flatMap和map来表达结合性操作比较困难。但我们如果不从Monadic值M[A](Monadic value)而是循Monadic函数A=>M[B](Monadic function)来证明Monad结合性操作就容易多了。

A=>[B]是瑞士数学家Heinrich Kleisli法则的箭头(Kleisli Arrow)。我们可以用Kleisli Arrow来实现一个函数compose:

def compose[A,B,C](f: A=>[B], g: B=>M[C]): A=>M[C]。从函数款式看compose是一个Monadic函数组合。我们从返回值的类型A=>M[C]得出实现框架 a => ???;从传入参数类型 B=>M[C]可以估计是flatMap(M[A])(B=>M[C]; 所以:

1       def compose[A,B,C](f: A => M[B], g: B => M[C]): A => M[C] = {
2         a => flatMap(f(a))(g)
3       }

注意:compose的实现还是通过了flatMap这个主导Monad实例行为的函数。有了compose我们就可以证明:

compose(f,compose(g,h)) == compose(compose(f,g),h)

flatMap和compose是互通的,可以相互转换。我们可以用compose来实现flatMap:

1       def flatMapByCompose[A,B](ma: M[A])(f: A => M[B]): M[B] = {
2           compose((_ : Unit) => ma, f)(())
3       }

我们可以用例子来证明它们的互通性:

1  optionMonad.flatMap(Some(12)){a => Some(a + 10)}//> res12: Option[Int] = Some(22)
2  optionMonad.compose((_: Unit) => Some(12), { (a : Int) => Some(a + 10)}) (())
3                                                   //> res13: Option[Int] = Some(22)

至于Monad恒等性,我们已经得到了unit这个Monad恒等值:

def unit[A](a: A): M[A]。通过unit我们可以证明Monad的左右恒等:

compose(f,unit) == f

compose(unit,f) == f

由于compose是通过flatMap实现的。compose + unit也可以成为Monad最基本组件。实际上还有一组基本组件join + map + unit:

1      def join[A](mma: M[M[A]]): M[A] = flatMap(mma) {ma => ma}

又是通过flatMap来实现的。

我们同样可以用join来实现flatMap和compose:

1       def flatMapByJoin[A,B](ma: M[A])(f: A => M[B]): M[B] = {
2           join(map(ma)(f))
3       }
4       def composeByjoin[A,B,C](f: A => M[B], g: B => M[C]): A => M[C] = {
5           a => join(map(f(a))(g))
6       }

仔细观察函数款式(signature),推导并不难。map A=>M[B] >>> M[M[B]],实际上join是个展平函数M[M[A]] >>> M[A]。

虽然有三种基本组件,我还是比较倾向于flatMap,因为只要能flatMap就是Monad。对我来说Monadic programming就是flatMap programming,其中最重要的原因是scala的for-comprehension。for-comprehension是scala的特点,只要是Monad实例就可以用for-comprehension,也可以说只要能flatMap就可以吃到for-comprehension这块语法糖。我们用一个比较复杂但实用的数据类型来说明:

在前面我们曾经实现了State类型。而且我们也实现了State类型的map, flatMap这两个函数:

 1 case class State[S, A](run: S => (A, S)) {
 2   def map[B](f: A => B): State[S, B] =
 3     State(s => {
 4       val (a, s1) = run(s)
 5       (f(a), s1)
 6     })
 7   def flatMap[B](f: A => State[S, B]): State[S, B] =
 8     State(s => {
 9       val (a, s1) = run(s)
10       f(a).run(s1)
11 }) }

既然实现了flatMap, 那么State就可以是Monad的了吧。我们试着建一个State Monad实例:

State类定义是这样的:case class State[S,+A](run: S => (A, S)) 

val StateMonad = new Monad[State[???, 糟糕,Monad[M[_]],M是个接受一个类参数的高阶类型,而State[S,A]是个接受两个类参数的高阶类型,该怎么办呢?我们可以这样解释State:State[S,_]:实际上State[S,_]是一组不同S的State[A],换句话说:State不只有一个Monad实例而是一类的Monad实例。我们可以这样表述这类的Monad:

1   class StateMonad[S] {
2       type StateS[A] = State[S,A]
3       val monad = new Monad[StateS] {
4         def unit[A](a: A): StateS[A] = State(s => (a,s))
5           def flatMap[A,B](ma: StateS[A])(f: A => StateS[B]): StateS[B] = flatMap(ma)(f)
6       }
7   }

我们可以这样使用以上的State Monad:StateMonad[List[Int]].monad

在上面我们遇到的问题是由于State类型与Monad M[_]类型不兼容引起的。这个问题会被scala编译器的类系统(type system)逮住,然后终止编译过程。是不是能从解决类系统问题方面着手呢?我们可以用type lambda来糊弄一下类系统:

1   def StateMonad[S] = new Monad[({type StateS[A]=State[S,A]})#StateS] {
2     def unit[A](a: A) = State(s => (a,s))
3     def flatMap[A,B](sa: State[S,A])(f: A => State[S,B]): State[S,B] = flatMap(sa)(f)
4   }

看,在Monad类参数里糊弄了类系统后,StateMonad内部沿用了State正常表述,没任何变化。type lambda在scalaz里使用很普遍,主要还是解决了数据类型参数不匹配问题。

实现了State Monad后我们可以看个相关例子:

 1   val intStateMonad = StateMonad[Int]             //> intStateMonad  : ch6.state.Monad[[A]ch6.state.State[Int,A]] = ch6.state$$an
 2                                                   //| onfun$main$1$$anon$2@7946e1f4
 3   def zipWithIndex[A](as: List[A]): List[(Int,A)] = {
 4       as.foldLeft(intStateMonad.unit(List[(Int, A)]()))((acc,a) => for {
 5           n <- getState
 6           xs <- acc
 7           _ <- setState(n+1)
 8       } yield((n,a) :: xs)).run(0)._1.reverse
 9   }                                               //> zipWithIndex: [A](as: List[A])List[(Int, A)]
10     
11   val lines=List("the quick","fox is","running","and runnng","...")
12                                                   //> lines  : List[String] = List(the quick, fox is, running, and runnng, ...)
13   zipWithIndex(lines)                             //> res3: List[(Int, String)] = List((0,the quick), (1,fox is), (2,running), (3
14                                                   //| ,and runnng), (4,...))

说明:foldLeft(z:B)(f:(B,A)=>B)的z是个intStateMonad实例类型B,所以foldLeft的操作函数就是:(intStateMonad,A)=>intStateMonad,我们可以使用for-comprehension。这个操作函数的返回结果是个intStateMonad实例;所以我们可以用State类的run(0)来运算State转换;State的状态起始值是0。

以上的例子做了些什么:它把List[String]转成了List[(Int,String)],把List[String]中每一个字串进行了索引。在这个例子里我们了解了Monad的意义:

1、可以使用for-comprehension

2、支持泛函式的循序命令执行流程,即:在高阶类结构内部执行操作流程。flatMap在这里起了关键作用,它确保了流程环节间一个环节的输出值成为另一个环境的输入值

那么我们可不可以说:Monad就是泛函编程中支持泛函方式流程式命令执行的特别编程模式。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端正义联盟

我来重新学习 javascript 的面向对象(part 5)

这是最后的最后了,我会顺便总结一下各种继承方式的学习和理解。(老板要求什么的,管他呢)

721
来自专栏nnngu

经典Java面试题收集

2、访问修饰符public,private,protected,以及不写(默认)时的区别?

3518
来自专栏cmazxiaoma的架构师之路

你应该会的一道多线程笔试题

2043
来自专栏有趣的django

8.python面向对象编程

基本概念 Class 类 一个类即是对一类拥有相同属性的对象的抽象、蓝图、原型。在类中定义了这些对象的都具备的属性(variables(data))、共同的方法...

2917
来自专栏Android知识点总结

Java总结之容器家族--Collection

Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性...

792
来自专栏Golang语言社区

interface引发的事件真相

流动的水没有形状,漂流的风找不到踪迹,一切代码都了然于心,我们在写代码的时候,总是有一种思维定式陪伴左右,在对事物做判断的时候,往往这种思维定式会往正向或反向做...

3216
来自专栏海天一树

小朋友学Java(6):封装

面向对象有三大特征:封装(Encapsulation)、继承(Inheritance)和多态(Polymorphism)。 本节讲封装。 程序1 class W...

3058
来自专栏青枫的专栏

JVM对异常的默认处理方案

701
来自专栏一个会写诗的程序员的博客

13.11 Scala混用Java的集合类调用scala的foreach遍历问题13.11 Scala混用Java的集合类调用scala的foreach遍历问题问题描述原因分析解决方案

由于都运行在JVM上,Java与Scala之间基本能做到无缝的集成,区别主要在于各自的API各有不同。由于Scala为集合提供了更多便捷的函数,因此,Java与...

564
来自专栏HappenLee的技术杂谈

C++雾中风景11:厘清C++之中的类型转换

开门见山,先聊聊笔者对类型转换的看法吧。从设计上看,一门面向对象的语言是不一样提供类型转换的,这种方式破坏了类型系统。C++为了兼容C也不得不吞下这个苦果,在实...

913

扫码关注云+社区