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

    简单来说:Monad就是泛函编程中最概括通用的数据模型(高阶数据类型)。它不但涵盖了所有基础类型(primitive types)的泛函行为及操作,而且任何高阶类或者自定义类一旦具备Monad特性就可以与任何类型的Monad实例一样在泛函编程中共同提供一套通用的泛函编程方式。所以有人把泛函编程视作Monadic Programming也不为过之。那么,具体什么是Monad呢?

    在前面我们讨论过Monoid,我们说过它是一个特殊的范畴(Category),所有数据类型的Monoid实例都共同拥有一套Monoid特有的操作及遵循一套Monoid行为定律。这样我们可以把Monoid视为一个抽象数据模型,在泛函算法中使用特殊的Monoid实例就可以达到预期的效果而不需要修改算法。那么可以说Monad就是一个比Monoid更概括、更抽象、覆盖范畴更广的高阶数据类型了。

    实际上在设计泛函库组件(combinator)时,我们会尽量避免重复编码,实现方式就是把通用或共性的操作抽取出来形成一些新的高阶类型(higher types),也就是新的抽象类型(Abstraction)。这样我们可以在不同的组件库中对同类操作共同使用这些通用的类型了。让我们先看看以下的一个抽象过程:

我们在前面讨论过一些数据类型。它们都有一个共同的函数:map

1   def map[A,B](la: List[A])(f: A => B): List[B]
2   def map[A,B](oa: Option[A])(f: A => B): Option[B]
3   def map[A,B](pa: Par[A])(f: A => B): Par[B]
4   def map[A,B](sa: State[S,A])(f: A => B): State[S,B]

这几个函数都具有高度相似的款式(signature),不同的是它们施用的具体数据类型。那么我们应该可以把这个map抽象出来:通过增加一个高阶类型Functor,用它来概括实现map:

1   trait Functor[F[_]] {
2       def map[A,B](a: F[A])(f: A => B): F[B]
3   }

注意在上面的map例子里的施用类型都是高阶类型;List[A]、Option[A]、Par[A] ...都是F[A]这种形式。所以Functor的类参数是F[_],即: Functor[List], Functor[Option], Functor[Par] ...,这里面F[_]就是F[A],A可以是任何类型。我们可以设计一个List的Functor实例:

1   object ListFunctor extends Functor[List] {
2       def map[A,B](la: List[A])(f: A => B): List[B] = la map f
3   }

把F换成List就可以了。其它类型的Functor实例:

1  object OptionFunctor extends Functor[Option] {
2       def map[A,B](oa: Option[A])(f: A => B): Option[B] = oa map f
3   }
4   object StreamFunctor extends Functor[Stream] {
5       def map[A,B](sa: Stream[A])(f: A => B): Stream[B] = sa map f
6   }

我们只需要对不同类型的操作使用对应的Functor实例就可以了:

1 ListFunctor.map(List(1,2,3)){_ + 10}             //> res0: List[Int] = List(11, 12, 13)
2  OptionFunctor.map(Some(1)){_ + 10}               //> res1: Option[Int] = Some(11)

操作模式是一致相同的。不过讲实在话,上面的这些实例都没什么意义,因为施用的具体类型本身就支持map。也就是说List,Option等本身就是Functor。换句话讲就是:它们都可以map,所以都是Functor。看看下面怎么使用Functor吧:

1   trait Functor[F[_]] {
2       def map[A,B](a: F[A])(f: A => B): F[B]
3       def unzip[A,B](fab: F[(A,B)]): (F[A],F[B]) = {
4         (map(fab){a => a._1},map(fab){a => a._2})
5       }
6   }

在这个例子中我特意把整个trait申明放了进去。这里的map还是抽象的,意味着还需要在具体的类型实例里实现。我们在设计unzip时是针对F的。在trait Functor里我们可以肯定F[(A,B)]支持map,所以我们才可以完成unzip函数的实现。这就是抽象的作用。当我们使用unzip时只要确定传入的参数fab是Functor就行了。这样unzip可以支持所有封装(A,B)的Functor:

1 ListFunctor.unzip(List((1,10),(2,20),(3,30)))    //> res0: (List[Int], List[Int]) = (List(1, 2, 3),List(10, 20, 30))
2  OptionFunctor.unzip(Some((1,2)))                 //> res1: (Option[Int], Option[Int]) = (Some(1),Some(2))

讲到这里,这个Functor跟Monad有什么关系吗?不过这种抽象的目的和模式可能跟Monad有什么关联吧?那么再往下推导:在之前的数据类型设计里我们曾想碰到很多map2函数:

1  def map2[A,B,C](la: List[A], lb: List[B])(f: (A,B) => C): List[C] = {
2       la flatMap {a => lb map { b => f(a,b) }}
3   }
4   def map2[A,B,C](oa: Option[A], ob: Option[B])(f: (A,B) => C): Option[C] = {
5       oa flatMap{a => ob map { b => f(a,b) }}
6   }
7   def map2[A,B,C](pa: Par[A], pb: Par[B])(f: (A,B) => C): Par[C] = {
8       pa flatMap{a => pb map { b => f(a,b) }}
9   }

看看这些map2函数:不但款式相同,实现方法也是相同的。不同的还是具体施用受体的数据类型。看来我们还是因为各种数据类型的不同而重复编写了map2组件。我们应该想办法一次实现map2后让所有数据类型实例都可以使用,从而彻底避免重复编码。可以肯定的是这些办法一定跟共性抽象有关。

  在前面那些章节的讨论中我们一直针对某些数据类型的特性设计最基本的操作函数或组件。因为各种数据类型的不同我们重复编写了map2组件。现在我们看到map2是可以用flatMap和map来实现的。那么flatMap和map就是最基本最通用的组件了吗?事实上map可以用flatMap和unit来实现:

1   def map[A,B](pa: Par[A])(f: A => B): Par[B] = {
2       flatMap(pa) { a => unit(f(a)) }
3   }

那么我们就先选择unit + flatMap作为最基本组件。当然,从前面的推导中我们可以得出unit + flatMap基本组件比Functor更抽象(更概括),因为map可以用unit + flatMap来实现。我们称这个抽象模型为Monad,它继承了Functor的特性,是Functor,因为Monad可以map。我们可以先用trait来表达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   }

在这个trait里unit和flatMap是抽象的。这意味着各类型的Monad实例必须实现unit和flatMap,并且会自动获取map和map2两个组件。

 1  val listMonad = new Monad[List] {
 2      def unit[A](a: A) = List(a)
 3      def flatMap[A,B](la: List[A])(f: A => List[B]): List[B] = {
 4           la flatMap f
 5      }
 6   }                                               //> listMonad  : ch11.monad.Monad[List] = ch11.monad$$anonfun$main$1$$anon$1@253
 7                                                   //| 0c12
 8   
 9   listMonad.map(List(1,2,3)){_ + 10}              //> res0: List[Int] = List(11, 12, 13)
10   listMonad.map2(List(1,2),List(3,4)){(a,b) => List(a,b)}
11                                                   //> res1: List[List[Int]] = List(List(1, 3), List(1, 4), List(2, 3), List(2, 4))
12                                                   //| 

的确我们从listMonad中自动获得了可用的map和map2.

optionMonad是这样的:

1  val optionMonad = new Monad[Option] {
2       def unit[A](a: A) = Some(a)
3       def flatMap[A,B](oa: Option[A])(f: A => Option[B]): Option[B] = {
4           oa flatMap f
5       }
6   }                                               //> optionMonad  : ch11.monad.Monad[Option]{def unit[A](a: A): Some[A]} = ch11.m
7                                                   //| onad$$anonfun$main$1$$anon$2@4e04a765
8   optionMonad.map(Some(1)){a => a + 10}           //> res2: Option[Int] = Some(11)
9   optionMonad.map2(Some(1),Some(2)){_ + _}        //> res3: Option[Int] = Some(3)

现在我们似乎可以说任何可以flatMap(具备flatMap函数)的数据类型都是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       def travers[A,B](la: List[A])(f: A => M[B]): M[List[B]] = {
14           la.foldRight(unit(Nil: List[B])){(a,b) => map2(f(a),b){_ :: _}}
15       }
16       def replicateM[A](n: Int, ma: M[A]): M[List[A]] = {
17           if (n == 0) unit(Nil)
18           else map2(ma,replicateM(n-1,ma)) {_ :: _}
19       }
20       def factor[A,B](ma: M[A], mb: M[B]): M[(A,B)] = {
21           map2(ma,mb){(a,b) => (a,b)}
22       }
23       def cofactor[A,B](e: Either[M[A],M[B]]): M[Either[A,B]] = {
24           e match {
25               case Right(b) => map(b){x => Right(x)}
26               case Left(a) => map(a){x => Left(x)}
27           }
28       }
29   }

可以看出,我们新增加的组件都是以unit + flatMap这两个基础组件实现的,都是更高阶的组件。所以是不是可以说Monadic programming 就是 flatMap Programming呢?

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏逸鹏说道

Python3 与 C# 扩展之~基础拓展

看着小张准备回家换衣服了,小明有点失落,又有点孤单,于是说道:“逗逼张,你还要听吗?我准备讲类相关的知识了,这些可是我课后自学的哦~”

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

深圳scala-meetup-20180902(3)- Using heterogeneous Monads in for-comprehension with Monad Transformer

  scala中的Option类型是个很好用的数据结构,用None来替代java的null可以大大降低代码的复杂性,它还是一个更容易解释的状态表达形式,比如在读...

552
来自专栏技术/开源

从C#到TypeScript - 装饰器

从C#到TypeScript - 装饰器 在C#里面如果想要不直接修改类或方法,但给类或方法添加一些额外的信息或功能,可以想到用Attribute,这是一个十分...

20310
来自专栏java学习

Java每日一练(2017/7/21)

聊天系统 ●我希望大家积极参与答题!有什么不懂可以加小编微信进行讨论 ★珍惜每一天,拼搏每一天,专心每一天,成功每一 如果你是初学者,或者是自学者!你可以加小编...

3274
来自专栏灯塔大数据

技术 | Python从零开始系列连载(十三)

如果是你自己定义函数,函数名要符合变量命名规则,并且不能是系统关键字(在jupyter中,打出系统关键字是绿色的)

782
来自专栏编程

Python函数之一切皆对象

今天我们要讲的是 对象 避免误会,常老师先澄清一下,这里面说的对象指的是object,不是你的lover,也不是你的sweetheart…… 有的小伙伴可能会觉...

1797
来自专栏HTML5学堂

面向对象系列讲解—认识对象

HTML5学堂:面向对象、原型、继承应该说是属于JavaScript最底层的知识和概念,对于这些知识,在我们没有触碰的时候的确觉得是比较困难的,包括在学习的过程...

2824
来自专栏Python小白进阶之旅

Python面试必备,看完轻轻松松拿到10k

平时我们几乎不可能用到的东西,像那些类里面的魔法方法,你还记得几个,这些可都是面试必备啊~

4028
来自专栏Ryan Miao

Java8学习(4)-Stream流

Stream和Collection的区别是什么 流和集合的区别是什么? 粗略地说, 集合和流之间的差异就在于什么时候进行计算。集合是一个内存中的数据结构,它包...

6047
来自专栏web前端教室

挖坑无止境,来看看这个《this的指向》

无事乱翻书,偶然发现这个东西: var length = 10; function fn() { console.log(this.length); }...

1846

扫码关注云+社区