## 动力学知识库

` 1 trait Monad[M[_]] extends Functor[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 map[A,B](ma: M[A])(f: A => B): M[B] = { 5 flatMap(ma){a => unit(f(a))} 6  } 7 def map2[A,B,C](ma: M[A], mb: M[B])(f: (A,B) => C): M[C] = { 8 flatMap(ma) { a => map(mb){ b => f(a,b) }} 9  }10 def sequence[A](lm: List[M[A]]): M[List[A]] = {11 lm.foldRight(unit(Nil: List[A])){(a,b) => map2(a,b){_ :: _} }12  }13 //递归方式sequence14 def sequence_r[A](lm: List[M[A]]): M[List[A]] = {15  lm match {16 case Nil => unit(Nil: List[A])17 case h::t => map2(h,sequence_r(t)){_ :: _}18  }19  }20 //高效点的sequence（可以并行运算Par）21 def bsequence[A](iseq: IndexedSeq[M[A]]): M[IndexedSeq[A]] = {22 if (iseq.isEmpty) unit(Vector())23 else if (iseq.length == 1) map(iseq.head){Vector(_)}24 else {25 val (l,r) = iseq.splitAt(iseq.length / 2)26 map2(bsequence(l),bsequence(r)) {_ ++ _}27  }28  }29 def traverse[A,B](la: List[A])(f: A => M[B]): M[List[B]] = {30 la.foldRight(unit(Nil: List[B])){(a,b) => map2(f(a),b){_ :: _}}31  }32 def replicateM[A](n: Int, ma: M[A]): M[List[A]] = {33 if (n == 0) unit(Nil)34 else map2(ma,replicateM(n-1,ma)) {_ :: _}35  }36 def factor[A,B](ma: M[A], mb: M[B]): M[(A,B)] = {37 map2(ma,mb){(a,b) => (a,b)}38  }39 def cofactor[A,B](e: Either[M[A],M[B]]): M[Either[A,B]] = {40  e match {41 case Right(b) => map(b){x => Right(x)}42 case Left(a) => map(a){x => Left(x)}43  }44  }45 }`

1. sequence >>> 用map2实现 >>> 用flatMap实现：

对于List: sequence[A](lm: List[M[A]]): M[List[A]] >>> sequence[A](lm: List[List[A]]): List[List[A]]

>>> map2(list(list1),list(list2)){_ :: _} ,把封装在list里的list进行元素分拆交叉组合，

例：(List(List(1,2),List(3,4)) >>> List[List[Int]] = List(List(1, 3), List(1, 4), List(2, 3), List(2, 4)）

sequence的作用体现在List.map2功能。而List.map2则是由List.flatMap实现的。所以sequence的行为还是依赖于List实例中flatMap的实 现方法

对于Option: sequence[A](lm: List[M[A]]): M[List[A]] >>> sequence[A](lm: List[Option[A]]): List[Option[A]]

>>> map2(list(opton1),list(option2)){_ :: _} ,把封装在list里的元素option值串成list，

例：(List(Some(1),Some(2),Some(3)) >>> Option[List[Int]] = Some(List(1, 2, 3))

由于sequence的行为还是依赖于实例中flatMap的实现，Option 的特点：flatMap None = None 会产生如下效果：

List(Some(1),None,Some(3)) >>> Option[List[Int]] = None

对于Par: sequence[A](lm: List[M[A]]): M[M[A]] >>> sequence[A](lm: List[Par[A]]): List[Par[A]]

>>> map2(list(par1),list(par2)){_ :: _} ,运行封装在list里的并行运算并把结果串成list，

这里Par.flatMap的功能是运行par，run(par)。这项功能恰恰是并行运算Par的核心行为。

A=>[B]是瑞士数学家Heinrich Kleisli法则的箭头（Kleisli Arrow）。我们可以用Kleisli Arrow来实现一个函数compose:

def compose[A,B,C](f: A=>[B], g: B=>M[C]): A=>M[C]。从函数款式看compose是一个Monadic函数组合。我们从返回值的类型A=>M[C]得出实现框架 a => ???；从传入参数类型 B=>M[C]可以估计是flatMap(M[A])(B=>M[C]； 所以：

`1 def compose[A,B,C](f: A => M[B], g: B => M[C]): A => M[C] = {2 a => flatMap(f(a))(g)3 }`

compose(f,compose(g,h)) == compose(compose(f,g),h)

flatMap和compose是互通的，可以相互转换。我们可以用compose来实现flatMap：

`1 def flatMapByCompose[A,B](ma: M[A])(f: A => M[B]): M[B] = {2 compose((_ : Unit) => ma, f)(())3 }`

`1 optionMonad.flatMap(Some(12)){a => Some(a + 10)}//> res12: Option[Int] = Some(22)2 optionMonad.compose((_: Unit) => Some(12), { (a : Int) => Some(a + 10)}) (())3 //> res13: Option[Int] = Some(22)`

compose(f,unit) == f

compose(unit,f) == f

`1 def join[A](mma: M[M[A]]): M[A] = flatMap(mma) {ma => ma}`

`1 def flatMapByJoin[A,B](ma: M[A])(f: A => M[B]): M[B] = {2  join(map(ma)(f))3  }4 def composeByjoin[A,B,C](f: A => M[B], g: B => M[C]): A => M[C] = {5 a => join(map(f(a))(g))6 }`

` 1 case class State[S, A](run: S => (A, S)) { 2 def map[B](f: A => B): State[S, B] = 3 State(s => { 4 val (a, s1) = run(s) 5  (f(a), s1) 6  }) 7 def flatMap[B](f: A => State[S, B]): State[S, B] = 8 State(s => { 9 val (a, s1) = run(s)10  f(a).run(s1)11 }) }`

State类定义是这样的：case class State[S,+A](run: S => (A, S))

`1 class StateMonad[S] {2 type StateS[A] = State[S,A]3 val monad = new Monad[StateS] {4 def unit[A](a: A): StateS[A] = State(s => (a,s))5 def flatMap[A,B](ma: StateS[A])(f: A => StateS[B]): StateS[B] = flatMap(ma)(f)6  }7 }`

`1 def StateMonad[S] = new Monad[({type StateS[A]=State[S,A]})#StateS] {2 def unit[A](a: A) = State(s => (a,s))3 def flatMap[A,B](sa: State[S,A])(f: A => State[S,B]): State[S,B] = flatMap(sa)(f)4 }`

` 1 val intStateMonad = StateMonad[Int] //> intStateMonad : ch6.state.Monad[[A]ch6.state.State[Int,A]] = ch6.state\$\$an 2 //| [email protected] 3 def zipWithIndex[A](as: List[A]): List[(Int,A)] = { 4 as.foldLeft(intStateMonad.unit(List[(Int, A)]()))((acc,a) => for { 5 n <- getState 6 xs <- acc 7 _ <- setState(n+1) 8 } yield((n,a) :: xs)).run(0)._1.reverse 9 } //> zipWithIndex: [A](as: List[A])List[(Int, A)]1011 val lines=List("the quick","fox is","running","and runnng","...")12 //> lines : List[String] = List(the quick, fox is, running, and runnng, ...)13 zipWithIndex(lines) //> res3: List[(Int, String)] = List((0,the quick), (1,fox is), (2,running), (314 //| ,and runnng), (4,...))`

1、可以使用for-comprehension

2、支持泛函式的循序命令执行流程，即：在高阶类结构内部执行操作流程。flatMap在这里起了关键作用，它确保了流程环节间一个环节的输出值成为另一个环境的输入值