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

    上两期我们讨论了Monad。我们说Monad是个最有概括性(抽象性)的泛函数据类型,它可以覆盖绝大多数数据类型。任何数据类型只要能实现flatMap+unit这组Monad最基本组件函数就可以变成Monad实例,就可以使用Monad组件库像for-comprehension这样特殊的、Monad具备的泛函式数据结构内部的按序计算运行流程。针对不同的数据类型,flatMap+unit组件实现方式会有所不同,这是因为flatMap+unit代表着承载数据类型特别的计算行为。之前我们尝试了List,Option,甚至更复杂的State等数据类型的Monad实例,过程中我们分别对这些数据类型的unit和flatMap进行了实现。实际上flatMap+unit并不是Monad唯一的最基本组件函数,还有compose+unit及join+map+unit这两组Monad最基本组件函数,因为我们可以用这些组件相互实现:

 1   trait Monad[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 compose[A,B,C](f: A => M[B], g: B => M[C]): A => M[C] = {
 5           a => { flatMap(f(a))(g)}
 6       }
 7       def flatMapByCompose[A,B](ma: M[A])(f: A => M[B]): M[B] = {
 8           compose(((_):Unit) => ma,f)(())
 9       }
10       def join[A](mma: M[M[A]]): M[A] = {
11           flatMap(mma)(ma => ma)
12       }
13       def map[A,B](ma: M[A])(f: A => B): M[B] = {
14           flatMap(ma)(a => unit(f(a)))
15       }
16       def flatMapByJoin[A,B](ma: M[A])(f: A => M[B]): M[B] = {
17           join(map(ma)(a => f(a)))
18       }
19       def composeByJoin[A,B,C](f: A => M[B], g: B => M[C]): A => M[C] = {
20           a => { join(map(f(a))(g)) }
21       }
22   }

所以,我们可以通过直接对数据类型实现join+map+unit或compose+unit来产生Monad实例。

Monad也是Functor,因为我们可以用flatMap+unit来实现map。现在我们可以把Monad trait 改成 extends Functor:

1   trait Functor[F[_]] {
2       def map[A,B](fa: F[A])(f: A => B): F[B]
3   }
4   trait Monad[M[_]] extends Functor[M]{
5       def unit[A](a: A): M[A]
6       def flatMap[A,B](ma: M[A])(f: A => M[B]): M[B]
7       def map[A,B](ma: M[A])(f: A => B): M[B] = {
8           flatMap(ma)(a => unit(f(a)))
9       }

由于Monad是个超概括的数据类型,必须兼容各种计算模式,无法专注针对一些特殊的操作模式。在泛函编程模式中最具有特点的就是在一个封闭结构内运行函数。其中比较明显的就是map2这个函数了:

1       def map2[A,B,C](ma: M[A], mb: M[B])(f: (A,B) => C): M[C] = {
2           flatMap(ma)(a => map(mb)(b => f(a,b)))
3       }

map2把两个封在高阶类型结构里的元素通过运行f函数结合起来。完成操作后产生的结果仍然保持结构的完整性。这是一种典型的泛函编程函数施用模式(idiomatic function application)。由于这种函数施用模式在泛函编程中使用非常广泛,所以我们特别将这种模式的组件库独立出来并称之为Applicative。从前面的讨论我们可以注意到很多数据类型Monad实例的组件函数都可以用map2和unit来实现,如:

1       def sequence[A](lma: List[M[A]]): M[List[A]] = {
2           lma.foldRight(unit(List[A]()))((a,ma) => map2(a,ma)(_ :: _))
3       }
4       def traverse[A,B](la: List[A])(f: A => M[B]): M[List[B]] = {
5           la.foldRight(unit(List[B]()))((a,mb) => map2(f(a),mb)(_ :: _))
6       }

虽然在我们的例子里map2是通过flatMap+map实现的,实际上很多数据类型都可以直接实现map2,就像这样:

1  def Map2[A,B,C](ma: Option[A], mb: Option[B])(f: (A,B) => C): Option[C] = {
2       (ma,mb) match {
3           case (Some(a),Some(b)) => Some(f(a,b))
4           case _ => None
5       }
6   }

那么map2+unit会不会也是Monad的最基本组件呢?答案是否定的,因为用map2+unit是无法实现flatMap、join及compose的。

因为我们能够用flatMap来实现map2,所以Monad就是Applicative。但反之Applicative不一定是Monad。既然我们希望提高泛函施用模式的效率,那我们就先从函数施用开始。先看看map,map2,flatMap这三个函数:

1   def map[A,B]      (ma: M[A])       (f: A => B)    : M[B]
2   def map2[A,B,C](ma: M[A], mb: M[B])(f: (A,B) => C): M[C]
3   def flatMap[A,B]  (ma: M[A])       (f: A => M[B]) : M[B]

map和map2都是正宗的在高阶数据类型结构内的函数施用,但flatMap的函数是 A=>M[B],会破坏结果的结构。例如:我们对一个有3个元素的List进行map操作,结果仍然是一个3个元素的List。但如果flatMap的话就可能会产生不同长度的List:

既然是更专注于函数施用,那么还有一种款式的函数是值得研究的:

1 def apply[A,B](fab: F[A => B])(fa: F[A]): F[B]

apply的施用函数是通过一个Monadic值传入的,这就使得apply比map更加强大,因为这个施用函数还带着F结构的作用。就拿Option来说:apply的施用函数可以是None而map无论如何都必须提供施用函数。这样一来apply会比map更加灵活和强大。以下就是Applicative trait:

 1   trait Applicative[F[_]] extends Functor[F] {
 2       def unit[A](a: A): F[A]
 3       def map2[A,B,C](fa: F[A], fb: F[B])(f: (A,B) => C): F[C] = {
 4           apply(fb)(map(fa)(f.curried))     //map(fa)(a => (b => c)) >>> F[A=>B]
 5       }
 6       def apply[A,B](fa: F[A])(fab: F[A =>B]): F[B] = {
 7  //         map2(fab,fa)((f,a) => f(a))
 8             map2(fab,fa)(_(_))
 9       }
10       def map[A,B](fa: F[A])(f: A => B): F[B] = {
11  //         map2(unit(f),fa)((f,a) => f(a))
12           map2(unit(f),fa)(_(_))
13       }
14       def mapByApply[A,B](fa: F[A])(f: A => B): F[B] = {
15           apply(fa)(unit(f))
16       }     
17   }

apply和map2可以相互实现。map可以用map2或apply来实现。所以Applicative extends Functor。下面我们来分析一下flatMap和map2的差别,这也代表着Monad和Applicative在行为上的区别。我们用Option来示范一下flatMap,map2及apply的分别:

 1 def Map2[A,B,C](ma: Option[A], mb: Option[B])(f: (A,B) => C): Option[C] = {
 2       (ma,mb) match {
 3           case (Some(a),Some(b)) => Some(f(a,b))
 4           case _ => None
 5       }
 6   }
 7   def apply[A,B](ma: Option[A])(f: Option[A => B]): Option[B] = {
 8       (ma,f) match {
 9           case (Some(a),Some(f)) => Some(f(a))
10           case _ => None
11       }
12   }
13   def flatMap[A,B](ma: Option[A])(f: A => Option[B]): Option[B] = {
14       ma match {
15           case Some(a) => f(a)
16           case _ => None
17       }
18   }

apply和map的运算都依赖于两个传入参数的状态:只有两个参数都是Some时才会在Some结构内部进行运算。而flatMap的传入函数A=>Option[B]是否运行则依赖于ma状态是否Some,而传入函数运行的结果又依赖于ma内元素A的值。所以我们确定Applicative可以保持运算结果的结构不变,而Monad有可能会造成运算结果的结构变化。

我们知道可以用map2把两个Monatic值M[A],M[B]施用函数(A+B)=>C连接起来,概括这个模式map3,map4,map5...都可以起到相同作用:

我们曾经用map2实现过map3,map4,map5:

 1     def map3[A,B,C,D](ma: M[A], mb: M[B], mc: M[C])(f: (A,B,C) => D): M[D] = {
 2         map2(ma, 
 3           map2(mb,mc){(b,c) => (b,c)}
 4           ){(a,bc) => {
 5            val (b,c) = bc
 6              f(a,b,c)
 7           }}
 8     }
 9     def map4[A,B,C,D,E](ma: M[A], mb: M[B], mc: M[C], md: M[D])(f: (A,B,C,D) => E): M[E] = {
10         map2(ma,
11           map2(mb,
12           map2(mc,md){(c,d) => (c,d)}
13           ){(b,cd) => (b,cd)}
14           ){(a,bcd) => {
15               val (b,(c,d)) = bcd
16               f(a,b,c,d)
17           }}
18     }
19     def map5[A,B,C,D,E,F](ma: M[A], mb: M[B], mc: M[C], md: M[D], me: M[E])(f: (A,B,C,D,E) => F): M[F] = {
20         map2(ma,
21           map2(mb,
22           map2(mc,
23           map2(md,me){(d,e) => (d,e)}
24           ){(c,de) => (c,de)}
25           ){(b,cde) => (b,cde)}
26           ){(a,bcde) => {
27               val (b,(c,(d,e))) = bcde
28               f(a,b,c,d,e)
29           }}
30     }

以上的实现方式很规范:通过map2连续地对M[_]进行函数施用产生结果。用map2来进行函数施用相对比较复杂,那么用专门的泛函施用apply会不会更好些呢?让我们来试着推导一下:

首先我们可以把一个三个入参数的函数curry一下:f(A,B,C) >>> A => B => C => D >>> f.curried。然后把函数放到unit里:

unit(f.curried) = M[A=>B=>C]。apply(M[A])(M[A=>B]):M[B]。我们可以针对每个M值分步施用apply:A=>B=>C >>> A=>BC >>> BC=B=>C,apply(M[A])(unit(f.curried))=M[B=>C],那么可以用apply来实现map3,map4,map5:

 1       def map3[A,B,C,D](ma: F[A], mb: F[B], mc: F[C])(f: (A,B,C) => D): F[D] = {
 2           apply(mc)(apply(mb)
 3               (apply(ma)(unit(f.curried))))
 4       }
 5       def map4[A,B,C,D,E](ma: F[A], mb: F[B], mc: F[C],md: F[D])(f: (A,B,C,D) => E): F[E] = {
 6           apply(md)(apply(mc)
 7           (apply(mb)
 8           (apply(ma)(unit(f.curried)))))
 9       }
10       def map5[A,B,C,D,E,G](ma: F[A], mb: F[B], mc: F[C],md: F[D], me: F[E])(f: (A,B,C,D,E) => G): F[G] = {
11           apply(me)(apply(md)
12           (apply(mc)
13           (apply(mb)
14           (apply(ma)(unit(f.curried))))))
15       }

使用apply就清楚很多了,我们只需要把一个函数进行curry后用unit升格然后通过Monadic值把参数传进去就可以在泛函结构内运算函数了。

因为我们可以用flatMap来实现map2和apply,所以所有Monad都是Applicative。由于我们在Monad组件库里已经实现许多有用的组件函数,我们就不需要在Applicative库里重复了。我们可以对Monad extends Applicative:

 1  trait Monad[M[_]] extends Applicative[M]{
 2       def unit[A](a: A): M[A]
 3       def flatMap[A,B](ma: M[A])(f: A => M[B]): M[B] = {
 4           join(map(ma)(f))
 5       }
 6       def compose[A,B,C](f: A => M[B], g: B => M[C]): A => M[C] = {
 7           a => { flatMap(f(a))(g)}
 8       }
 9       def join[A](mma: M[M[A]]): M[A] = {
10           flatMap(mma)(ma => ma)
11       }
12        override def apply[A,B](ma: M[A])(fab: M[A => B]): M[B] = {
13           flatMap(fab)(f => flatMap(ma)(a => unit(f(a))))
14       }     

这样所有Monad都可以是Applicative。但是,有些Applicative未必是Monad,因为我们可能无法用某些类型Applicative实例的map2或apply来实现flatMap、join、compose。

我们还是用一个实际的例子来解释Monad与Applicative的不同行为:

如果我们设计一个网页的登陆页面,用户需要填写name,birthdate,phone三个字段。提交页面后由系统验证录入信息。我们前面使用过类型Either,刚好用来返回系统验证结果。系统需要对三个字段进行验证,我们可以先把这三个验证函数的款式写出来:

 1  implicit def eitherMonad[E] = new Monad[({type l[V] = Either[E,V]})#l] {
 2       def unit[A](a: A) = Right(a)
 3       def flatMap[A,B](ea: Either[E,A])(f: A => Either[E,B]): Either[E,B] = {
 4           ea match {
 5               case Right(a) => f(a)
 6               case Left(e) => Left(e)
 7           }
 8       }
 9   }
10   def validateName(name: String): Either[String,String]
11   def validatebirthdate(birthdate: Date): Either[String,Date]
12   def validatePhone(phone: String): Either[String,String]

这三个验证函数都返回Either类型。因为有implict eitherMonad实例所以可以flatMap验证函数的结果:

1 validateName(field1) flatMap (f1 =>
2 validateBirthdate(field2) flatMap (f2 =>
3 validatePhone(field3) map (WebForm(_, _, _))

WebForm是个构建函数(constructor): case class WebForm(name: String, birthdate: Date, phone: String)。如果我们像上面那样逐个flatMap验证函数结果的话,从flatMap的具体实现代码可以看出:如果validName返回错误的话,下面的validateBirthdate, validatePhone都不会运行。系统直接将错误返回用户,用户要先改正了第一个错误再提交后系统继续下一个字段的验证。如果需要填写多个字段的信息表格什么的就更凸显麻烦了。如果我们用Applicative风格:

1 apply(apply(apply((WebForm(_, _, _)).curried)(
2   validateName(field1)))(
3   validateBirthdate(field2)))(
4   validatePhone(field3))

使用apply三个验证函数之间就没有任何依赖和先后顺序。我们可以任何顺序来运行验证函数而且可以确保三个验证函数都会运行。我们从flatMap和apply不同的行为模式来证明Monad操作和Applicative操作是不尽相同的。

我们继续把这个例子推进下去:我们希望系统一次性运行所有验证函数。如果出现一或多个错误就同时返回所有错误信息。由于可能需要返回多条错误信息,Either类型已经不足以用了。我们试着加一个新的错误处理数据类型:

1 trait Validation[+E,+A]
2 case class Failure[E](head: E, tail: Vector[E]) extends Validation[E,Nothing]
3 case class success[A](a: A) extends Validation[Nothing,A]

Validation类型的Failure可以容纳多条数据。注意 +E,+A使我们可以代入Nothing: Validate[E,Nothing],Validation[Nothing,A]。

我们先看看Applicative实例:

 1 implicit def validationApplicative[E] = new Applicative[({type l[A] = Validation[E,A]})#l] {
 2     def unit[A](a: A) = Success(a)
 3   def map2[A,B,C](fa: Validation[E,A], fb: Validation[E,B])(f: (A,B) => C): Validation[E,C] = {
 4     (fa,fb) match {
 5         case (Success(a),Success(b)) => Success(f(a,b))
 6         case (Failure(h1,t1),Failure(h2,t2)) => Failure(h1, t1 ++ Vector(h2) ++ t2)
 7         case (e@Failure(_,_),_) => e
 8         case (_,e@Failure(_,_)) => e
 9     }
10   }
11 }

map2+unit是Applicative的最基本组件函数。我们只要实现这两个函数就行了。

我们接着完成这个validateWebForm函数:

 1 trait Validation[+E,+A]
 2 case class Failure[E](head: E, tail: Vector[E]) extends Validation[E,Nothing]
 3 case class Success[A](a: A) extends Validation[Nothing,A]
 4 implicit def validationApplicative[E] = new Applicative[({type l[A] = Validation[E,A]})#l] {
 5     def unit[A](a: A) = Success(a)
 6   def map2[A,B,C](fa: Validation[E,A], fb: Validation[E,B])(f: (A,B) => C): Validation[E,C] = {
 7     (fa,fb) match {
 8         case (Success(a),Success(b)) => Success(f(a,b))
 9         case (Failure(h1,t1),Failure(h2,t2)) => Failure(h1, t1 ++ Vector(h2) ++ t2)
10         case (e@Failure(_,_),_) => e
11         case (_,e@Failure(_,_)) => e
12     }
13   }
14 }
15 import java.util.Date  
16 case class WebForm(name: String, birthdate: Date, phone: String)
17 
18 def validateName(name: String): Validation[String, String] = {
19   if (name != "")
20        Success(name)
21   else Failure("Name cannot be empty", Vector())
22 }
23 
24 def validateBirthdate(birthdate: String): Validation[String, Date] = {
25   try {
26     import java.text._
27     Success((new SimpleDateFormat("yyyy-MM-dd")).parse(birthdate))
28   } catch {
29     case e => Failure("Birthdate must be in the form yyyy-MM-dd", Vector())
30   }
31 }
32 def validatePhone(phoneNumber: String): Validation[String, String] = {
33   if (phoneNumber.matches("[0-9]{10}"))
34        Success(phoneNumber)
35   else Failure("Phone number must be 10 digits", Vector())
36 }
37 def validateWebForm(name: String, birthdate: String, phone: String): Validation[String, WebForm] = {
38     apply(validateName(name))
39      (apply(validateBirthdate(birthdate))
40      (apply(validatePhone(phone))((WebForm(_,_,_)).curried)))))
41 }

这就是一个实实在在的Applicative应用例子。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏芋道源码1024

【追光者系列】HikariCP 源码分析之故障检测那些思考 fail fast & allowPoolSuspension

由于时间原因,本文主要内容参考了 https://segmentfault.com/a/1190000013136251 ,并结合一些思考做了增注

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

FunDA(2)- Streaming Data Operation:流式数据操作

   在上一集的讨论里我们介绍并实现了强类型返回结果行。使用强类型主要的目的是当我们把后端数据库SQL批次操作搬到内存里转变成数据流式按行操作时能更方便、准确、...

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

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

    在上一节我们介绍了Monad。我们知道Monad是一个高度概括的抽象模型。好像创造Monad的目的是为了抽取各种数据类型的共性组件函数汇集成一套组件库从...

19410
来自专栏逆向与安全

某地理位置模拟APP从壳流程分析到破解

在我们拿到一个APP准备破解时一般得安装运行,程序运行后须要注册用户,随便注册一个用户登录,以下是APP须要购买vip才能使用的大概情况。

860
来自专栏Java Web

《编写高质量代码》学习笔记(1)

前言 看大神推荐的书单中入门有这么一本书,所以决定把这本书的精华(自认为很有用的点),或许是我自己现在能用到的点都提炼出来,供大家参考学习。 以下内容均出自《...

3644
来自专栏码匠的流水账

聊聊jesque的event机制

jesque-2.1.2-sources.jar!/net/greghaines/jesque/worker/WorkerEvent.java

451
来自专栏码匠的流水账

聊聊rocketmq的FileAppender

org/apache/rocketmq/logging/inner/LoggingBuilder.java

431
来自专栏码云1024

RandomAccessFile&IO流&排序&方法论

2677
来自专栏码匠的流水账

聊聊micrometer的HistogramGauges

针对springboot应用,配备有各种export的AutoConfiguration,详见org.springframework.boot.actuate....

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

Scalaz(35)- Free :运算-Trampoline,say NO to StackOverflowError

   在前面几次讨论中我们介绍了Free是个产生Monad的最基本结构。它的原理是把一段程序(AST)一连串的运算指令(ADT)转化成数据结构存放在内存里,这个...

1978

扫码关注云+社区