泛函编制程序情势,泛函数据类型

   
前面大家谈论了Applicative。Applicative
正是某种Functor,因为我们得以用map二来达成map,所以Applicative能够map,正是Functor,叫做Applicative
Functor。大家又说富有Monad都以Applicative,因为大家能够用flatMap来达成map二,但不是享有数据类型的flatMap都可以用map二达成,所以反之不是富有Applicative都是Monad。Applicative重视于各连串型的函数施用,也正是map。包括普通函数的行使及在高阶类型结构内的函数施用,还有多参数函数的总是使用。表面上看来Monad已经覆盖了Functor,
Applicative。恐怕正是因为Monad的效果太强大了,所以Monad的函数组合(functional
composition)万分简单。大家不得不从Applicative来赢得函数组合那部分的能力了。

   
经过了壹段时间的学习,大家了然了1俯十皆是泛函数据类型。我们驾驭,在装有编制程序语言中,数据类型是支持软件编程的根基。同样,泛函数据类型Foldable,Monoid,Functor,Applicative,Traversable,Monad也是大家现在进入实际泛函编制程序的必需。在前方对那些数据类型的探索中大家发现:

   
大家先研商一下Applicative的一对平整:

一、Monoid的重要用途是在举行折叠(Foldable)算法时对可折叠结构内成分进行函数施用(function
application)、

一、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的1种。

三、Applicative extends
Functor,同样都以对F[_}内成分进行函数施用。不相同的是使用函数是包嵌在高阶类型的(F[A
=>
B])。Applicative能够对负有可观光结构(Traversable),包罗可折叠结构(Foldable),嵌入的因素举行函数施用。Applicative好像比Monoid成效尤为强有力,那样,Applicative的重要用途之一应该是对可观光结构内成分进行函数施用。

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

四、Monad应该是泛函编制程序中最重点的数据类型。Monad
extends Applicative,那样,Monad就含有了Functor,
Applicative的属性。更关键的是,Monad成就了for-comprehension。通过for-comprehension能够兑现泛函风格的“行令编程情势(imperative
programming)。泛函编制程序与价值观的行令编制程序在情势上最大的个别就是在泛函编制程序中尚无变量评释(variable
declaration),变量是包嵌在1个布局里的(MyData(data)),得评释那个结构(trait
MyData[String])。所以泛函编制程序的吩咐执行都是在有个别布局内部开始展览的。Monad组件库中的组件首要协助那种布局内部运算风格。不能利用行令编制程序情势迟早对泛函编制程序进程导致不便,但Monad使for-comprehension成为只怕,而在for-comprehension内足以兑现行反革命令编制程序,所以泛函编制程序被叫做Monadic
programming并不为过。

二、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))。map三正是函数升阶组合:把函数
(_(_(_))) >>> (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此外3个烈性浮未来针对可观光类型(traversable
type)内部因素的函数施用(map)。与可折叠类型(foldable
type)相相比,traversable类型特别空虚,能遮住类型越多数据类型。Foldable类型的map用Monoid实现,但Monoid不可能完全落实Traversable类型的map。Traversable类型的map是通过Applicative完结。Traversable覆盖了Foldable,所以Foldable只是Traversable的里边1种案例。那么大家就看看那些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实例时最棒完成map二,因为它的函数款式更简约清晰。而在拓展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个破例的种类呢?

 

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必须是2个Applicative

Maybe正是Option。由于scala标准Curry已经有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相互能够兑现。

大家看来了1段嵌在for-comprehension内的行令运算。但运算的条件须求从表面上还十分的小概明确。那么,那段运算的另贰个本子恐怕拥有启示:

sequence和traverse能够并行达成,但sequence的达成须求使用map。大家得以试着在trait
Traverse里金玉满堂3个暗中同意的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]lovebet,(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就足以兑现1个暗许的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,map二操作:

能够看的出来,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那么大家能够把它作为任何别的Monad1样与其余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的函数语法11分类似。实际上全部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函数

 

二、tb 长度超越 ta :
用上面包车型大巴zipLX570函数

 

 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分别同时举办函数施用。