泛函编程（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应用例子。

时间： 2024-10-17 23:37:22

泛函编程（25）－泛函数据类型－Monad－Applicative的相关文章

泛函编程（5）－数据结构（Functional Data Structures)

  编程即是编制对数据进行运算的过程.特殊的运算必须用特定的数据结构来支持有效运算.如果没有数据结构的支持,我们就只能为每条数据申明一个内存地址了,然后使用这些地址来操作这些数据,也就是我们熟悉的申明变量再对变量进行读写这个过程了.试想想如果没有数据结构,那我们要申明多少个变量呢.所以说,数据结构是任何编程不可缺少的元素.     泛函编程使用泛函数据结构(Functional Data Structure)来支持泛函程序.泛函数据结构的特点是"不可变特性"(Immutability)

泛函编程（28）－粗俗浅解：Functor, Applicative, Monad

  经过了一段时间的泛函编程讨论,始终没能实实在在的明确到底泛函编程有什么区别和特点:我是指在现实编程的情况下所谓的泛函编程到底如何特别.我们已经习惯了传统的行令式编程(imperative programming),总是先入为主的认为软件编程就是一行接着一行的更改某些变量状态指令:明刀明枪,字里行间目的和方式都很明确.我们就以一步步更改程序状态的方式,一行一行的拼凑指令:这就是典型的行令式编程了. 泛函编程,顾名思义,就是用一个个函数来编程.讲的再深入点就是通过函数组合来更改程序状态.什么意思

泛函编程（23）－泛函数据类型－Monad

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

泛函编程（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:

泛函编程（27）－泛函编程模式－Monad Transformer

  经过了一段时间的学习,我们了解了一系列泛函数据类型.我们知道,在所有编程语言中,数据类型是支持软件编程的基础.同样,泛函数据类型Foldable,Monoid,Functor,Applicative,Traversable,Monad也是我们将来进入实际泛函编程的必需.在前面对这些数据类型的探讨中我们发现: 1.Monoid的主要用途是在进行折叠(Foldable)算法时对可折叠结构内元素进行函数施用(function application). 2.Functor可以对任何高阶数据类型F[

泛函编程（32）－泛函IO：IO Monad

 由于泛函编程非常重视函数组合(function composition),任何带有副作用(side effect)的函数都无法实现函数组合,所以必须把包含外界影响(effectful)副作用不纯代码(impure code)函数中的纯代码部分(pure code)抽离出来形成独立的另一个纯函数.我们通过代码抽离把不纯代码逐步抽离向外推并在程序里形成一个纯代码核心(pure core).这样我们就可以顺利地在这个纯代码核心中实现函数组合.IO Monad就是泛函编程处理副作用代码的一种手段.我们

泛函编程（34）－泛函变量：处理状态转变－ST Monad

  泛函编程的核心模式就是函数组合(compositionality).实现函数组合的必要条件之一就是参与组合的各方程序都必须是纯代码的(pure code).所谓纯代码就是程序中的所有表达式都必须是Referentially Transparent(RT,等量可替换的),它的意思是:在一段程序p中,所有的表达式e都可以用e的运算结果替代而不影响到p的运算结果,那么e就是RT等量可替换的,也就是说程序p是由纯代码组成的.但如果程序p中包含了一些变量,这些变量的状态就会影响到程序中e的运算结果,那

泛函编程（21）－泛函数据类型－Monoid

    Monoid是数学范畴理论(category theory)中的一个特殊范畴(category).不过我并没有打算花时间从范畴理论的角度去介绍Monoid,而是希望从一个程序员的角度去分析Monoid以及它在泛函编程里的作用.从这个思路出发我们很自然得出Monoid就是一种数据类型,或者是一种在泛函编程过程中经常会遇到的数据类型:当我们针对List或者loop进行一个数值的积累操作时我们就会使用到Monoid.实际上Monoid就是List[A] => A的抽象模型.好了,我们就不要越描

泛函编程（30）－泛函IO：Free Monad－Monad生产线

 在上节我们介绍了Trampoline.它主要是为了解决堆栈溢出(StackOverflow)错误而设计的.Trampoline类型是一种数据结构,它的设计思路是以heap换stack:对应传统递归算法运行时在堆栈上寄存程序状态,用Trampoline进行递归算法时程序状态是保存在Trampoline的数据结构里的.数据结构是在heap上的,所以可以实现以heap换stack的效果.这种以数据结构代替函数调用来解决问题的方式又为泛函编程提供了更广阔的发展空间.     我们知道,任何涉及IO的运