泛函编程(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 条评论
登录 后参与评论

相关文章

来自专栏偏前端工程师的驿站

JS魔法堂:再识Number type

Brief                                   本来只打算理解JS中0.1 + 0.2 == 0.300000000000000...

2085
来自专栏软件开发

JavaSE学习总结(八)—— 异常处理(Exception)

一、理解异常及异常处理的概念 异常就是在程序的运行过程中所发生的不正常的事件,它会中断正在运行的程序。 异常不是错误 程序中关键的位置有异常处理,提高程序的稳定...

2109
来自专栏逆向技术

C++反汇编第五讲,认识多重继承,菱形继承的内存结构,以及反汇编中的表现形式.

      C++反汇编第五讲,认识多重继承,菱形继承的内存结构,以及反汇编中的表现形式. 目录:   1.多重继承在内存中的表现形式     多重继承在汇编中...

1937
来自专栏大数据学习笔记

Java程序设计(Java9版):第2章 数据类型与运算符(Data types and Operators)

第2章 数据类型与运算符(Data types and Operators) I think everybody in this country should ...

2255
来自专栏jessetalks

Javascript基础回顾 之(一) 类型

  本来是要继续由浅入深表达式系列最后一篇的,但是最近团队突然就忙起来了,从来没有过的忙!不过喜欢表达式的朋友请放心,已经在写了:) 在工作当中发现大家对Jav...

3677
来自专栏柠檬先生

Python 基础 Dict 和 Set 类型

python 什么是dict   例如:     d = { 'Adam': 95, 'Lisa': 85, 'Bart': 59 }     我们把名称称为k...

2789
来自专栏blackheart的专栏

[C#3] 1-扩展方法

1.从DEMO开始 先看一个扩展方法的例子: 1 class Program 2 { 3 public static void Main(...

20510
来自专栏十月梦想

php循环

853
来自专栏函数式编程语言及工具

泛函编程(23)-泛函数据类型-Monad

    简单来说:Monad就是泛函编程中最概括通用的数据模型(高阶数据类型)。它不但涵盖了所有基础类型(primitive types)的泛函行为及操作,而且...

1888
来自专栏菜鸟前端工程师

JavaScript学习笔记023-对象方法0包装对象0静态属性

942

扫码关注云+社区