泛函编程(26)-泛函数据类型-Monad-Applicative Functor Traversal泛函编程(27)-泛函编程模式-Monad Transformer

   
前面我们谈谈了Applicative。Applicative
就是某种Functor,因为我们可为此map2来促成map,所以Applicative可以map,就是Functor,叫做Applicative
Functor。我们而说所有Monad都是Applicative,因为我们好为此flatMap来实现map2,但切莫是具有数据类型的flatMap都可以用map2实现,所以反而的无是富有Applicative都是Monad。Applicative注重于各种类型的函数施用,也就是map。包括常见函数的行使及以高阶类型结构外之函数施用,还有多参数函数的连续用。表面上看来Monad已经蒙了Functor,
Applicative。可能就是是坐Monad的效力最好强劲了,所以Monad的函数组合(functional
composition)非常简单。我们只好从Applicative来得到函数组合这片之力量了。

   
经过了一段时间的习,我们询问了一如既往层层泛函数据类型。我们解,在有着编程语言中,数据类型是支持软件编程的基础。同样,泛函数据类型Foldable,Monoid,Functor,Applicative,Traversable,Monad也是咱前进来实际泛函编程的必不可少。在前边对这些数据类型的追究中我们发现:

   
我们先行研一下Applicative的局部条条框框:

1、Monoid的主要用途是以开展折叠(Foldable)算法时对可折结构内元素进行函数施用(function
application)、

1、map的恒等定律:map(v)(x
=> x) === v

2、Functor可以对其它高阶数据类型F[_]内的元素进行日常函数(A
=> B)施用(map)

   map(v)(f) ===
apply(unit(f))(v),
就是说把一个函数f用unit升阶后apply就是map。apply就是map的同种植。

3、Applicative extends
Functor,同样都是针对性F[_}内元素进行函数施用。不同的是利用函数是包嵌在高阶类型的(F[A
=>
B])。Applicative可以本着负有可观光结构(Traversable),包括可折结构(Foldable),嵌入的素进行函数施用。Applicative好像比较Monoid功能尤为强,这样,Applicative的主要用途之一应该是指向而观光结构内元素进行函数施用。

 
 Applicative的恒等定律:apply(unit(x => x))(v) === v

4、Monad应该是泛函编程中极度重点的数据类型。Monad
extends Applicative,这样,Monad就含有了Functor,
Applicative的性能。更关键的凡,Monad成就了for-comprehension。通过for-comprehension可以实现泛函风格的“行令编程模式(imperative
programming)。泛函编程与民俗的行令编程在模式及无限老的各自就是于泛函编程中莫变量声明(variable
declaration),变量是包嵌在一个布局里之(MyData(data)),得申明这个布局(trait
MyData[String])。所以泛函编程的授命执行还是于片构造中开展的。Monad组件库中的组件主要支撑这种结构中运算风格。无法运用行令编程模式必然对泛函编程过程导致诸多不便,但Monad使for-comprehension成为可能,而以for-comprehension内足以实现行令编程,所以泛函编程被名Monadic
programming并不为过。

2、Applicative的函数组合:如果我们具有以下标准:

看个for-comprehension例子:

   f类型 = F[A =>
B], g类型 = F[B => C],x类型 = F[A]。那么:

1   val compute: Option[Int] = {
2    for {
3        x <- getNextNumber
4        x1 <- getNextNumber
5        y <- shapeIt(x)
6        z <- divideBy(y,x1)
7    } yield z
8   }

   apply(map2(f,g)(_
compose _))(x) === apply(f)(apply(g)(x)),或者另行直接一点:

次第在for{}内同步一步运行,典型的行令模式。

 
 map3(f,g,x)(_(_(_))) === f(g(x))。map3就是函数升阶组合:把函数
(_(_(_))) >>> (a,b,c) => d
在高阶类型结构外开展组合。

得说:for-comprehension组成了一个嵌入式的简便行令编程语言,而有它的Monad同时还要规定了其的语意(symatics)。

先期看看两只Applicative组件的兑现:

如上的例子中for-comprehension是出于Option[Int]概念的,那么,如果这for-comprehension是由一个上述Monad组成的呢?例如:IO[Option[A]],这个有点像做(Monad
composition)。那么我们便先从Monad composition开始吧,看怎么将简单个Monad
compose起来。

 1   def product[F[_],G[_]](a1: Applicative[F],a2: Applicative[G]) = new Applicative[({type l[V] = (F[V], G[V])})#l] {
 2       def unit[A](a: A) = (a1.unit(a), a2.unit(a))
 3       override def apply[A,B](aa: (F[A],G[A]))(fg: (F[A => B], G[A => B])) = {
 4           (a1.apply(aa._1)(fg._1), a2.apply(aa._2)(fg._2))
 5       }
 6       override def map2[A,B,C](fga: (F[A],G[A]), fgb: (F[B],G[B]))(f: (A,B) => C): (F[C],G[C]) = {
 7           (a1.map2(fga._1,fgb._1)(f), a2.map2(fga._2,fgb._2)(f))
 8       }
 9   }                                               //> product: [F[_], G[_]](a1: ch12.ex1.Applicative[F], a2: ch12.ex1.Applicative
10                                                   //| [G])ch12.ex1.Applicative[[V](F[V], G[V])]
11   def compose[F[_],G[_]](a1: Applicative[F], a2: Applicative[G]) = new Applicative[({type l[V] = F[G[V]]})#l] {
12       def unit[A](a: A) = a1.unit(a2.unit(a))
13       override def map2[A,B,C](fga: F[G[A]], fgb: F[G[B]])(f: (A,B) => C): F[G[C]] = {
14           a1.map2(fga,fgb)((ga,gb) => a2.map2(ga,gb)(f))
15       }
16   }                                               //> compose: [F[_], G[_]](a1: ch12.ex1.Applicative[F], a2: ch12.ex1.Applicative
17                                                   //| [G])ch12.ex1.Applicative[[V]F[G[V]]]

怎么compose呢?先看看Functor的composition:

对于Applicative
F,G来说 (F[A],G[A]),
F[G[A]]啊还是Applicative。通过对个别个Applicative进行函数组合后形成一个重新高阶的Applicative。这个Applicative和另普通的Applicative一样可实现多参数函数的升阶连续使用。

 1     trait Functor[F[_]] {
 2         def map[A,B](fa: F[A])(f: A => B): F[B]
 3     }
 4   def compose[F[_],G[_]](m: Functor[F], n: Functor[G]) =
 5       new Functor[({type l[x] = F[G[x]]})#l] {
 6           override def map[A,B](fga: F[G[A]])(f: A => B) = {
 7               m.map(fga)(ga => n.map(ga)(f))
 8           }
 9       }                                           //> compose: [F[_], G[_]](m: ch12.ex2.Functor[F], n: ch12.ex2.Functor[G])ch12.e
10                                                   //| x2.Functor[[x]F[G[x]]]

Applicative另外一个血性体现于针对可观光类型(traversable
type)内部因素的函数施用(map)。与可折叠类型(foldable
type)相较,traversable类型更加空虚,能遮住类型又多数据类型。Foldable类型的map用Monoid实现,但Monoid无法完全落实Traversable类型的map。Traversable类型的map是通过Applicative实现。Traversable覆盖了Foldable,所以Foldable只是Traversable的内同样种案例。那么我们不怕看看是Traversable类型:

咱清楚:只要实现了纸上谈兵函数map,就得形成Functor实例。这个Functor[({type l[x]
= F[G[x]]})#l]便是一个Functor实例,因为咱们可实现map[A,B](fga:
F[G[A]])(f: A =>
B)。有了此Functor实例,我们不怕得处理F[G[A]]这么类型的数据类型:

在面前我们谈论过的数据类型里,我们且见面兑现traverse,sequence这有限独函数。那是坐我们尝试将那些数据类型都改为Traversable类型。traverse,sequence的函数款式是这样的:

 1  val listFunctor = new Functor[List] {
 2       override def map[A,B](la: List[A])(f: A => B): List[B] = la.map(f)
 3   }                                               //> listFunctor  : ch12.ex2.Functor[List] = ch12.ex2$$anonfun$main$1$$anon$6@3c
 4                                                   //| bbc1e0
 5   val optionFunctor = new Functor[Option] {
 6       override def map[A,B](oa: Option[A])(f: A => B): Option[B] = oa.map(f)
 7   }                                               //> optionFunctor  : ch12.ex2.Functor[Option] = ch12.ex2$$anonfun$main$1$$anon$
 8                                                   //| 7@35fb3008
 9   
10   Option("abc").map(_.length)                     //> res4: Option[Int] = Some(3)
11   val fg = compose(listFunctor,optionFunctor)     //> fg  : ch12.ex2.Functor[[x]List[Option[x]]] = ch12.ex2$$anonfun$main$1$$anon
12                                                   //| $5@7225790e
13   
14   fg.map(List(Option("abc"),Option("xy"),Option("ryuiyty"))){ _.length }
15                                                   //> res5: List[Option[Int]] = List(Some(3), Some(2), Some(7))
1 def traverse[F[_],A,B](as: List[A], f: A => F[B]): F[List[B]]
2 def sequence[F[_],A](fas: List[F[A]]): F[List[A]]

 在上述我们用listFunctor处理了List[A]型数据,optionFunctor处理Option[A]。最终我们为此fg处理像List[Option[String]]品类的数。

咱试试实现Map类型的sequence:

 那么我们设能实现Monad[M[N]]的flatMap不就能获取这个Monad实例了呗:

1     def sequenceMap[K,V](mfv: Map[K,F[V]]): F[Map[K,V]] = {
2         mfv.foldLeft(unit(Map[K,V]())) {
3             case (fm,(k,fv)) => map2(fm, map(fv)(v => Map(k -> v)))((m,n) => m ++ n)
4         }
5     }

 

贯彻过程或者那个复杂的。这里小特别的地方用小心:在促成Applicative实例时最为好实现map2,因为它的函数款式更简约清晰。而当展开Applicative操作时以apply会更有益于。

1   def composeM[M[_],N[_](m: Monad[M], n: Monad[N]): Monad[({type l[x] = M[N[x]]})#l]= {
2       new Monad[({type l[x] = M[N[x]]})#l] {
3           def flatMap[A,B](mna: M[N[A]])(f: A => M[N[B]]): M[N[B]] = {
4             ????? !!!!!
5           }
6       }
7   } 

既然Traversable是那么地广泛,为什么未将她抽象出形成一个破例的品类为?

 

1 trait Traverse[T[_]] {
2       def sequence[AP[_]: Applicative, A](tapa: T[AP[A]]): AP[T[A]] 
3       def traverse[AP[_]: Applicative, A, B](ta: T[A])(f: A => AP[B]): AP[T[B]]
4   }

伤心的凡这次无法兑现flatMap。这个悲剧明确了想“Monad
do not
compose!”。那我们的Monadic语言梦想就这么快消了吧?实际上多独Monad定义的for-comprehension可以经过Monad
Transformer来实现。Monad
Transformer可以兑现多单Monad效果的丰富(stacking
effect)。好,那咱们就开看这个Monad Transformer吧:

这trait里之sequence,traverse函数与我们前实现的sequence和traverse有啊两样啊?

俺们先行实现一个Maybe
Monad:

F[_]变成了AP[_]:Applicative:就是说AP必须是一个Applicative

Maybe就是Option。由于scala标准库里已经发出Option类型,为免函数引用混扰,所以定义一个初的Monad。

List变成了T:trait
Traverse针对任何T[_],包括List,更包括了。以前的sequence和traverse都只是针对List,现在底Traverse类型可以进行概括所有T[_]这种类型。

 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     }    
 8     trait Maybe[+A] {
 9         def map[B](f: A => B): Maybe[B] ={
10             this match {
11                 case Just(a) => Just(f(a))
12                 case _ => Nada
13             }
14         }
15         def flatMap[B](f: A => Maybe[B]): Maybe[B] = {
16             this match {
17                 case Just(a) => f(a)
18                 case _ => Nada
19             }
20         }
21     }
22     case class Just[+A](a: A) extends Maybe[A]
23     case object Nada extends Maybe[Nothing]

我们摸索着实现这个Traverse类型:

咱们实现了Maybe类型的unit,map,flatMap,所以我们好于Maybe
Monad的环境里实现for-comprehension的运

1  trait Traverse[T[_]] {
2       def sequence[AP[_]: Applicative, A](tapa: T[AP[A]]): AP[T[A]] = traverse(tapa)(apa =>apa)
3       def traverse[AP[_]: Applicative, A, B](ta: T[A])(f: A => AP[B]): AP[T[B]] = sequence(map(ta)(f))
4       def map[A,B](ta: T[A])(f: A => B): T[B]
5   }

 

我们得以尝试着实现List,Option,Tree这几只Traverse类型实例:

1     val maybeFor: Maybe[Int] = for {
2         x <- Just(2)
3         y <- Just(5)
4         z = x * y
5     } yield z                                 //> maybeFor  : ch12.ex2.Maybe[Int] = Just(10)
 1  case class Tree[+A](head: A, tail: List[Tree[A]])
 2   object Traverse {
 3       val listTraverse = new Traverse[List] {
 4           override def traverse[AP[_],A,B](la: List[A])(f: A => AP[B])(implicit m: Applicative[AP]): AP[List[B]] = {
 5             la.foldLeft(m.unit(List[B]()))((a,b) => m.map2(f(b),a)(_ :: _))
 6           }
 7       }
 8       val optionTraverse = new Traverse[Option] {
 9           override def traverse[AP[_],A,B](oa: Option[A])(f: A => AP[B])(implicit m: Applicative[AP]): AP[Option[B]] = {
10               oa match {
11                   case Some(a) => m.map(f(a))(b => Some(b))
12                   case None => m.unit(None)
13               }
14           }
15       }     
16       val treeTraverse = new Traverse[Tree] {
17           override def traverse[AP[_],A,B](ta: Tree[A])(f: A => AP[B])(implicit m: Applicative[AP]): AP[Tree[B]] = {
18             m.map2(f(ta.head),listTraverse.traverse(ta.tail)(da => traverse(da)(f)))(Tree(_,_))
19           }
20       }

 

负有Traverse类型的实例只要实现traverse或sequence就可了,因为traverse和sequence相互可以兑现。

俺们来看了扳平段子嵌在for-comprehension内的行令运算。但运算的条件要求自外表上还无法一目了然。那么,这段运算的旁一个本子可能拥有启示:

sequence和traverse可以并行实现,但sequence的实现内需动用map。我们得试行着在trait
Traverse里心想事成一个默认的map函数:

1     val maybeMap: Maybe[Int] = {
2         Just(2).flatMap(x => Just(5).map(y => x * y))
3                                                   //> maybeMap  : ch12.ex2.Maybe[Int] = Just(10)
4     }

咱俩可以拿走一个Identity
Functor:type Id[A] = A,
这个事物存粹是为博F[A]如此个形象以便匹配类型款式。这样咱们可汲取一个Identity
Monad:

咱们懂得for-comprehension就是flatMap的方法糖。所以上述就是原始flatMap运算。从夫flatMap表达形式我们可以汲取每一样句子运算都必遵主导Monad的flatMap函数类型(signature),也就是说类型必须配合。

1      type Id[A] = A
2       val idMonad = new Monad[Id] {
3          def unit[A](a: A) = a  
4  //         override def flatMap[A,B](a: Id[A])(f: A => Id[B]): Id[B] = f(a)
5            override def flatMap[A,B](a: A)(f: A => B): B = f(a)
6       }

俺们再来一个熟悉的Monad,State
Monad:

raverse会保留Traverse类型的原本结构。这点于Traverse定律可以推导:针对Traverse[F],
xs类型是F[A]的话:

 

 traverse[Id,A,A](xs)(x
=> x) === xs >>> map(xs)(x => x) ===xs,
这不纵是Functor恒等定律也?也就是说把traverse需要之Applicative
Functor降到Id
Functor继traverse相当给map操作。换句话说Traverse可以概括Functor并且traverse操作而较map操作强大许多。

 1     type State[S,+A] = S => (A,S)
 2   object State {
 3       def getState[S]: State[S,S] = s => (s,s)
 4       def setState[S](s: S): State[S,Unit] = _ => ((),s)
 5   }
 6     class StateOps[S,A](sa: State[S,A]) {
 7         def unit(a: A) = (s: S) => (a,s)
 8         def map[B](f: A => B): State[S,B] = {
 9             s => {
10                 val (a,s1) = sa(s)
11                 (f(a),s1)
12             }
13         }
14         def flatMap[B](f: A => State[S,B]): State[S,B] = {
15             s => {
16                 val (a,s1) = sa(s)
17                 f(a)(s1)
18             }
19         }
20     def getState[S]: State[S,S] = s => (s,s)
21     def setState[S](s: S): State[S,Unit] = _ => ((),s)
22     }
23     implicit def toStateOps[S,A](sa: State[S,A]) = new StateOps(sa)
24                                                   //> toStateOps: [S, A](sa: ch12.ex2.State[S,A])ch12.ex2.StateOps[S,A]

这般咱们就此idMonad就可实现一个默认的map函数:

 

 1   trait Traverse[T[_]] extends Functor[T] {
 2       def sequence[AP[_]: Applicative, A](tapa: T[AP[A]]): AP[T[A]] = traverse(tapa)(apa =>apa)
 3       def traverse[AP[_]: Applicative, A, B](ta: T[A])(f: A => AP[B]): AP[T[B]] = sequence(map(ta)(f))
 4       def map[A,B](ta: T[A])(f: A => B): T[B] = traverse[Id,A,B](ta)(f)(idMonad)
 5       
 6       type Id[A] = A
 7       val idMonad = new Monad[Id] {
 8         def unit[A](a: A) = a
 9  //         override def flatMap[A,B](a: Id[A])(f: A => Id[B]): Id[B] = f(a)
10           override def flatMap[A,B](a: A)(f: A => B): B = f(a)
11       }
12   }

同我们得以为此State
Monad定义之for-comprehension进行行令编程:

注意:在scala语法中:

 

 def
traverse[AP[_]: Applicative, A, B](ta: T[A])(f: A => AP[B]):
AP[T[B]]

 1     import State._
 2     val stateFor: State[Int, Int] = for {
 3         x <- getState[Int]
 4         y = x * 5
 5         _ <- setState(x+1)
 6     } yield y                                 //> stateFor  : ch12.ex2.State[Int,Int] = <function1>
 7     
 8     
 9     stateFor(2)                               //> res0: (Int, Int) = (10,3)
10 
11 可以肯定这个State Monad for-comprehension内的行令运算同样需要遵循State Monad map, flatMap的类型匹配。

AP[_]:Applicative是context
bound, 相当于:

 

def
traverse[AP[_], A, B](ta: T[A])(f: A => AP[B])(implicit m:
Applicative[AP]): AP[T[B]]

可肯定者State
Monad for-comprehension内之行令运算同样要依照State Monad map,
flatMap的品种匹配。

所以:

那么我们下将及时有限只Monad在一个for-comprehension里运行。比如

 def map[A,B](ta:
T[A])(f: A => B): T[B] =
traverse[Id,A,B](ta)(f)(idMonad)

 1  val nocompileFor = {
 2       def remainder(a: Int, b: Int): Maybe[Int] = {
 3           a % b match {
 4               case 0 => Nada
 5               case r => Just(r)
 6           }
 7       }
 8       for {
 9           x <- getState[Int]    //State.flatMap
10           y <- remainder(x,2)   //Maybe.flatMap
11           z = x + y             //???.map
12           _ <- setState[Int](5) //State.flatMap
13       } yield y
14   }                                               

缘何用之context
bound
Applicative实例?实现traverse时得Applicative的map,map2操作:

可关押的出,flatMap的类别且乱了仿了。以上例子无法通过编译器。

1       val listTraverse = new Traverse[List] {
2         override def traverse[AP[_],A,B](la: List[A])(f: A => AP[B])(implicit m: Applicative[AP]): AP[List[B]] = {
3             la.foldLeft(m.unit(List[B]()))((a,b) => m.map2(f(b),a)(_ :: _))
4         }
5       }

釜底抽薪方案:Monad
Transformer:

本咱们经过Traverse类型可以兑现旅游(Traversal)那么Traverse和Foldable有什么界别吧?从表面上来拘禁Traverse应该比Foldable更迅捷,因为Foldable是由此Monoid来对组织外之元素进行函数施用的,而Applicative比Monoid更强有力。我们先行瞧Foldable最概括的操作函数foldMap:

面的挫败例子是要是化解State[Maybe[A]]这种类型的问题。我们不怕需一个State
Monad Transformer:

def foldMap[A,B](as: F[A])(f: A => B)(mb: Monoid[B]): B

 1  import StateT._
 2     trait StateT[M[_],S,A] {   // State Monad Transformer
 3       def apply(s: S): M[(A,S)]
 4       
 5         def map[B](f: A => B)(implicit m: Functor[M]): StateT[M,S,B] = {
 6             stateT( s => m.map(apply(s)){
 7                 case (a,s1) => (f(a),s1)
 8             })
 9         }
10         
11         def flatMap[B](f: A => StateT[M,S,B])(implicit m: Monad[M]): StateT[M,S,B] = {
12             stateT( s => m.flatMap(apply(s)){
13                 case (a,s1) => f(a)(s1)
14             })
15         }
16         
17     }
18   object StateT {
19       def stateT[M[_],S,A](f: S => M[(A,S)]): StateT[M,S,A] = {
20           new StateT[M,S,A] {
21               def apply(s: S) = f(s)
22           }
23       }
24       def liftM[M[_],S,A](ma: M[A])(implicit m: Monad[M]): StateT[M,S,A] = {
25             stateT(s => m.map(ma)(a => (a, s)))
26       }
27   }

又探traverse的函数款式:

 StateT是单State Monad
Transformer,同时StateT也是一个Monad实例,因为我们好兑现其的flatMap函数。既然StateT是只Monad实例,那我们便足以为此StateT来定义其的for-comprehension了:

 def traverse[AP[_]: Applicative, A, B](ta: T[A])(f: A =>
AP[B]): AP[T[B]]

 

苟我们将AP[A]交换一个特制的门类:type
ConstInt[A] = Int, 经过替换traverse就成了:

 1   val maybeState: StateT[Maybe,Int,Int] = {
 2     def getState[S]: StateT[Maybe,S,S] = stateT(s => Just((s,s)))
 3     def setState[S](s: S): StateT[Maybe,S,Unit] = stateT(s1 => Just(((),s)))
 4       def remainder(a: Int, b: Int): Maybe[Int] = {
 5           a % b match {
 6               case 0 => Nada
 7               case r => Just(r)
 8           }
 9       }
10       for {
11           x <- getState[Int]
12           y <- liftM[Maybe,Int,Int](remainder(x,2))
13           z = x + y
14           _ <- setState[Int](5)
15       } yield y
16   }                                               //> maybeState  : ch12.ex2.StateT[ch12.ex2.Maybe,Int,Int] = ch12.ex2$$anonfun$m
17                                                   //| ain$1$StateT$3$$anon$4@34b7bfc0
18  
19   maybeState(1)                                   //> res1: ch12.ex2.Maybe[(Int, Int)] = Just((1,5))
20   maybeState(0)                                   //> res2: ch12.ex2.Maybe[(Int, Int)] = Nada

 def traverse[A,B](fa: T[A])(f: A => Int): Int

 以上这for-comprehension是故StateT[Maybe,Int,Int]来定义的。那么所有以for-comprehension内之表达式右方就不能不是StateT类型。上面的getState,setState函数结果还是StateT类型,但remainder函数返回结果也是Maybe类型。所以我们之所以liftM把Maybe类型升格到StateT类型。liftM的函数定义如下:

经替换的traverse在函数款式上颇像foldMap。那么我们就炮制一个对任何B的类:

1       def liftM[M[_],S,A](ma: M[A])(implicit m: Monad[M]): StateT[M,S,A] = {
2             stateT(s => m.map(ma)(a => (a, s)))
3       }

 type Const[A,B] = A

liftM的企图就是拿一个Monad
M[A]升级成为StateT。上面的事例我们因而liftM把Monad
Maybe升格成StateT类型,这样任何for-comprehension内部有着表达式类型且相当了。注意StateT把State
Monad和外其他一个Monad合起来用:上面的例子用了Maybe。实际上StateT[M,S,A]里之M可以是Maybe也堪是Option,Either,Validation。。。那咱们尽管好获StateT[Option,Int,Int],StateT[Either,Int,Int]这些Monad
Transformer并当for-comprehension里体现这些构成Monad的功效。更着重之凡StateT是单Monad那么我们好将她当作任何其它Monad一样同其余Monad结合形成新的Monad
Transformer。

 

要是我们需要处理反的门类:Maybe[State],我们就待定义MaybeT。我们先行瞧MaybeT的品种款式:

所以者类别丰富Monoid实现一个Applicative实例:

 caseclass MaybeT[M[_],A](run:
M[Maybe[A]]) 这是Monad Transformer通用款式

 

俺们管同采取的Monad包嵌在参数里:

1   object Applicative {
2     type Const[A, B] = A
3         implicit def monoidApplicative[M](m: Monoid[M]) = 
4           new Applicative[({type alias[x] = Const[M,x]})#alias] {
5             def unit[A](a: A): M = m.zero
6             override def apply[A,B](m1: M)(m2: M): M = m.op(m1, m2)
7 //            override def map2[A,B,C](m1: M, m2: M)(f: (A,B) => C): M = m.op(m1, m2)
8         }
9   }
 1     case class MaybeT[M[_],A](run: M[Maybe[A]]) {
 2         def map[B](f: A => B)(implicit m: Functor[M]): MaybeT[M,B] = {
 3             MaybeT[M,B](m.map(run)(a => a map f))
 4         }
 5         def flatMap[B](f: A => MaybeT[M,B])(implicit m: Monad[M]): MaybeT[M,B] = {
 6             MaybeT[M,B](m.flatMap(run) {
 7                 case Just(a) => f(a).run
 8                 case Nada => m.unit(Nada)
 9             })
10         }
11     }

有矣这Applicative实例,我们便得当trait
Traverse里实现foldMap,也就是意味着Traverse可以extend Foldable了:

一旦就此Option作为中心Monad,那么我们可以计划一个Option的Monad
Transformer OptionT类型:

 1    trait Traverse[T[_]] extends Functor[T] with Foldable[T] {
 2     def sequence[AP[_]: Applicative, A](tapa: T[AP[A]]): AP[T[A]] = traverse(tapa)(apa => apa)
 3     def traverse[AP[_]: Applicative, A, B](ta: T[A])(f: A => AP[B]): AP[T[B]] = sequence(map(ta)(f))
 4     def map[A, B](ta: T[A])(f: A => B): T[B] = traverse[Id, A, B](ta)(f)(idMonad)
 5 
 6     type Id[A] = A
 7     val idMonad = new Monad[Id] {
 8       def unit[A](a: A) = a
 9       //         override def flatMap[A,B](a: Id[A])(f: A => Id[B]): Id[B] = f(a)
10       override def flatMap[A, B](a: A)(f: A => B): B = f(a)
11     }
12     import Applicative._
13     override def foldMap[A,B](ta: T[A])(f: A => B)(mb: Monoid[B]): B = {
14         traverse[({type alias[x] = Const[B,x]})#alias,A,Nothing](ta)(f)(monoidApplicative(mb))
15     }  
16   }
 1   case class OptionT[M[_],A](run: M[Option[A]]) {
 2       def map[B](f: A => B)(implicit m: Functor[M]): OptionT[M,B] = {
 3            OptionT[M,B](m.map(run)(a => a.map(f)))
 4       }
 5       def flatMap[B](f: A => OptionT[M,B])(implicit m: Monad[M]): OptionT[M,B] = {
 6           OptionT[M,B](m.flatMap(run) {
 7               case Some(a) => f(a).run
 8               case None => m.unit(None)
 9           })
10       }
11   }

既然Traverse已经席卷了Foldable,而且Traverse类型有比Foldable效率高,那么之后尽量使用Traverse这种类型。

不顾,只要我们能将共同使用的当即简单只Monad升格成靶子Monad
Transformer类型格式就可放心在for-comprehension中开展行令编程了。

 State能够生抢眼地针对高阶数据类型结构里因素进行函数施用同时以保障了运算状态数据。前面我们已经取得了State
Nonad实例。因为拥有Monad都是Applicative,所以当我们早已获得了State
Applicative
Functor实例。如果我们当游览(traverse)一个汇的经过中因故State
Applicative
Functor对集合元素进行操作而保护状态数据,那么以会见兑现强的高阶数据类型处理功能。我们先行押一个组合State的traverse函数:

 

1     def traverseS[S,A,B](ta: T[A])(f: A => State[S,B]): State[S,T[B]] = {
2         traverse[({type alias[x] = State[S,x]})#alias, A, B](ta)(f)(StateMonad)
3     }

 

咱们因此这个函数来旅游集合并标注行号:

 

1   def zipWithIndex[A](ta: T[A]): T[(A,Int)] = {
2         traverseS(ta)(a => for {
3           i <- getState
4           _ <- setState(i + 1)
5         } yield(a,i)
6         )).run(0)._1
7     }

 

又用此函数把T[A]转成List[A]:

 

1     def toList[A](ta: T[A]): List[A] = {
2         traverseS(ta)(a => for {
3           as <- getState[List[A]]
4           _ <- setState(a :: as) 
5         } yield()
6         )).run(List[A]())._2.reverse
7     } 

 

立即半单应用State的函数语法十分近乎。实际上有State游览(traversal)都死相似。我们好再进一步抽象:

 

 1    def mapS[S,A,B](ta: T[A], s: S)(f: (A,S) => (B,S)): (T[B],S) = {
 2         traverse(ta)(a => for {
 3           s1 <- getState
 4           (b,s2) = f(a,s1)
 5           _ <- setState(s2)
 6         } yield(b)
 7         )).run(s)
 8     }
 9     def zipWithIndex[A](ta: T[A]): T[(A,Int)] = {
10         mapS(ta,0)((a,s) => ((a,s),s+1))._1
11     }
12     def toList[A](ta: T[A]): List[A] = {
13         mapS(ta,List[A]())((a,s) => ((), a :: s)).reverse
14     }
15     def reverse[A](ta: T[A]): T[A] = {
16         mapS(ta,toList(ta))((_,s) => (s.head, s.tail))._1
17     }
18     def foldLeft[A,B](ta: T[A])(z: B)(f: (B,A) => B): B = {
19         mapS(ta,z)((a,b) => ((),f(b,a)))._2
20     }

 

故mapS重新实现zipWithIndex,toList,foldLeft就简单的基本上。mapS游览天生是反序的,所以reverse函数只要对T[A]于是mapS走相同糟糕就是实行了。

 

咱发现Traverse类型会保持其的布局,这是它们的不屈也是它的瑕疵。如果我们尝试将少独Traverse结构T[A],T[B]拼接成T[(A,B}]常就是会见发现是操作对T[A]和T[B]的长是生一定要求的。我们先试着用mapS来并接T[A],T[B]:

 

1    def zip[A,B](ta: T[A], tb: T[B]): T[(A, B)] =
2     (mapS(ta, toList(tb)) {
3       case (a, Nil) => sys.error("zip: Incompatible shapes.")
4       case (a, b :: bs) => ((a, b), bs)
5     })._1

 

咱得以看到:tb的长要等还是超ta。如此我们只有把此函数分拆成稀种植情景的处理函数:

 

1、ta 长度超过 tb :
用下面的zipL函数

 

2、tb 长度超过 ta :
用下面的zipR函数

 

 1   def zipL[A,B](ta: T[A], tb: T[B]): T[(A, Option[B])] =
 2     (mapS(ta, toList(tb)) {
 3       case (a, Nil) => ((a, None), Nil)
 4       case (a, b :: bs) => ((a, Some(b)), bs)
 5     })._1
 6 
 7   def zipR[A,B](ta: T[A], tb: T[B]): T[(Option[A], B)] =
 8     (mapS(tb, toList(ta)) {
 9       case (b, Nil) => ((None, b), Nil)
10       case (b, a :: as) => ((Some(a), b), as)
11     })._1

诸如此类咱们得出的T[(A,B)]其中T[A],T[B]欠出的一对就是用None来填补。

俺们能够如Monoid product
一样在针对一个可折叠结构进行旅游时对结构里因素一次性进行多次操作,我们一致好对可畅游结构(Traversable)在平等轮子游览时对组织里因素进行多次操作:

1   def fuse[M[_],N[_],A,B](ta: T[A])(f: A => M[B], g: A => N[B])
2                          (implicit m: Applicative[M], n: Applicative[N]): (M[T[B]], N[T[B]]) =
3     traverse[({type f[x] = (M[x], N[x])})#f, A, B](ta)(a => (f(a), g(a)))(product(m, n))

个别个Applicative实例通过product函数变成Applicative[(M,N)]实例。在traverse运行中m,n分别又展开函数施用。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

相关文章