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

   
前边大家斟酌了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标准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互相能够兑现。

笔者们看来了一段嵌在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 :
用下边包车型地铁zip中华V函数

 

 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)在一轮游览时对协会内部因素进行数14次操作:

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分别同反常间进行函数施用。