## 动力学知识库

`final case class WriterT[F[_], W, A](run: F[(W, A)]) { self =>...`

Writer是WriterT的一个F[_] >>> Id特例，那么它的款式也可以被视作这样：

`final case class Writer[W, A](run: (W, A)) { self =>`

` def flatMap[B](f: A => WriterT[F, W, B])(implicit F: Bind[F], s: Semigroup[W]): WriterT[F, W, B] =flatMapF(f.andThen(_.run))def flatMapF[B](f: A => F[(W, B)])(implicit F: Bind[F], s: Semigroup[W]): WriterT[F, W, B] =writerT(F.bind(run){wa =>val z = f(wa._2)F.map(z)(wb => (s.append(wa._1, wb._1), wb._2))})`

` type StateT[F[_], S, A] = IndexedStateT[F, S, S, A]type IndexedState[-S1, S2, A] = IndexedStateT[Id, S1, S2, A]/** A state transition, representing a function `S => (S, A)`. */type State[S, A] = StateT[Id, S, A]`

State是StateT的Id特殊案例，而StateT又是IndexedStateT的S1=S2特殊案例。那我们就从最概括的类型IndexedStateT开始介绍吧。下面是IndexedStateT的定义：scalaz/StateT.scala

`trait IndexedStateT[F[_], -S1, S2, A] { self =>/** Run and return the final value and state in the context of `F` */def apply(initial: S1): F[(S2, A)]/** An alias for `apply` */def run(initial: S1): F[(S2, A)] = apply(initial)/** Calls `run` using `Monoid[S].zero` as the initial state */def runZero[S <: S1](implicit S: Monoid[S]): F[(S2, A)] =run(S.zero)/** Run, discard the final state, and return the final value in the context of `F` */def eval(initial: S1)(implicit F: Functor[F]): F[A] =F.map(apply(initial))(_._2)/** Calls `eval` using `Monoid[S].zero` as the initial state */def evalZero[S <: S1](implicit F: Functor[F], S: Monoid[S]): F[A] =eval(S.zero)/** Run, discard the final value, and return the final state in the context of `F` */def exec(initial: S1)(implicit F: Functor[F]): F[S2] =F.map(apply(initial))(_._1)/** Calls `exec` using `Monoid[S].zero` as the initial state */def execZero[S <: S1](implicit F: Functor[F], S: Monoid[S]): F[S2] =exec(S.zero)...`

` def map[B](f: A => B)(implicit F: Functor[F]): IndexedStateT[F, S1, S2, B] = IndexedStateT(s => F.map(apply(s)) {case (s1, a) => (s1, f(a))})def flatMap[S3, B](f: A => IndexedStateT[F, S2, S3, B])(implicit F: Bind[F]): IndexedStateT[F, S1, S3, B] = IndexedStateT(s => F.bind(apply(s)) {case (s1, a) => f(a)(s1)})`

`object IndexedStateT extends StateTInstances with StateTFunctions {def apply[F[_], S1, S2, A](f: S1 => F[(S2, A)]): IndexedStateT[F, S1, S2, A] = new IndexedStateT[F, S1, S2, A] {def apply(s: S1) = f(s)}}`

`trait MonadState[F[_,_],S] extends Monad[({type f[x]=F[S,x]})#f] {def state[A](a: A): F[S, A] = bind(init)(s => point(a))def constantState[A](a: A, s: => S): F[S, A] = bind(put(s))(_ => point(a))def init: F[S, S]def get: F[S, S]def gets[A](f: S => A): F[S, A] = bind(init)(s => point(f(s)))def put(s: S): F[S, Unit]def modify(f: S => S): F[S, Unit] = bind(init)(s => put(f(s)))}object MonadState {def apply[F[_,_],S](implicit F: MonadState[F, S]) = F}`

`private trait StateTMonadState[S, F[_]] extends MonadState[({type f[s, a] = StateT[F, s, a]})#f, S] {implicit def F: Monad[F]def bind[A, B](fa: StateT[F, S, A])(f: A => StateT[F, S, B]): StateT[F, S, B] = fa.flatMap(f)def point[A](a: => A): StateT[F, S, A] = {lazy val aa = aStateT(s => F.point(s, aa))}def init: StateT[F, S, S] = StateT(s => F.point((s, s)))def get = initdef put(s: S): StateT[F, S, Unit] = StateT(_ => F.point((s, ())))override def modify(f: S => S): StateT[F, S, Unit] = StateT(s => F.point((f(s), ())))override def gets[A](f: S => A): StateT[F, S, A] = StateT(s => F.point((s, f(s))))}`

`1 type Stack = List[Int]2 def pop: State[Stack, Int] = State { case h::t => (t,h) }3 //> pop: => scalaz.State[Exercises.stateT.Stack,Int]4 def push(a: Int): State[Stack, Unit] = State { xs => (a :: xs, ()) }5 //> push: (a: Int)scalaz.State[Exercises.stateT.Stack,Unit]`

` 1 val prg = for { 2 _ <- push(1) 3 _ <- push(2) 4 _ <- push(3) 5 a <- pop 6 b <- get 7 _ <- pop 8 _ <- put(List(9)) 9 } yield b //> prg : scalaz.IndexedStateT[scalaz.Id.Id,Exercises.stateT.Stack,List[Int],E10 //| xercises.stateT.Stack] = [email protected]11 prg.run(List()) //> res2: scalaz.Id.Id[(List[Int], Exercises.stateT.Stack)] = (List(9),List(2,12 //| 1))`

prg只是一段功能描述，因为状态运算函数是个lambda: s => (s,a)。这里s是个未知数，它在for loop里逐层传递下去。运算结果需要通过运行run函数并提供初始状态值List()后才能获取，也就是说真正的运算是在运行run时才开始的。我们称run为程序prg的翻译器（interpreter），这是函数式编程的典型模式，这样可以把具体运算延到最后。

` 1 val prg = for { 2 _ <- push(1) 3 _ <- push(2) 4 _ <- push(3) 5 a <- pop 6 b <- get //(s,s) 7 c <- gets { s:Stack => s.length} //(s,s.length) 8 _ <- pop 9 _ <- put(List(9)) //(List(9),a)10 _ <- modify {s:Stack => s ++ List(10) } //(List(9,10),a)11 } yield c //> prg : scalaz.IndexedStateT[scalaz.Id.Id,Exercises.stateT.Stack,List[Int],I12 //| nt] = [email protected]13 prg.run(List()) //> res2: scalaz.Id.Id[(List[Int], Int)] = (List(9, 10),2)`

`1 val prg1 = for {2 _ <- push(1)3 _ <- push(2)4 _ <- push(3)5 a <- pop6 b <- if (a == 3 ) put(List(1,2,3)) else put(List(2,3,4))7 } yield b //> prg1 : scalaz.IndexedStateT[scalaz.Id.Id,Exercises.stateT.Stack,List[Int],8 //| Unit] = [email protected]9 prg1.run(List()) //> res4: scalaz.Id.Id[(List[Int], Unit)] = (List(1, 2, 3),())`

`private trait StateTMonadStateMonadPlus[S, F[_]] extends StateTMonadState[S, F] with StateTHoist[S] with MonadPlus[({type λ[α] = StateT[F, S, α]})#λ] {implicit def F: MonadPlus[F]def empty[A]: StateT[F, S, A] = liftM[F, A](F.empty[A])def plus[A](a: StateT[F, S, A], b: => StateT[F, S, A]): StateT[F, S, A] = StateT(s => F.plus(a.run(s), b.run(s)))}`

` def liftM[G[_], A](ga: G[A])(implicit G: Monad[G]): StateT[G, S, A] =StateT(s => G.map(ga)(a => (s, a)))`

IndexedStateT还有一个挺有趣的函数lift。在FP风格里lift总是起到搭建OOP到FP通道的作用。我们先来看个例子：

`1 def incr: State[Int,Int] = State { s => (s+1,s)}//> incr: => scalaz.State[Int,Int]2 incr.replicateM(10).evalZero[Int] //> res3: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)`

` incr.replicateM(10000).runZero[Int] //> java.lang.StackOverflowError`

` def lift[M[_]: Applicative]: IndexedStateT[({type λ[α]=M[F[α]]})#λ, S1, S2, A] = new IndexedStateT[({type λ[α]=M[F[α]]})#λ, S1, S2, A] {def apply(initial: S1): M[F[(S2, A)]] = Applicative[M].point(self(initial))}`

`1  import scalaz.Free.Trampoline2 incr.lift[Trampoline].replicateM(10).evalZero[Int]3 //> res4: scalaz.Free[Function0,List[Int]] = Gosub()`

` import scalaz.Free.Trampolineincr.lift[Trampoline].replicateM(10000).evalZero[Int].run.take(5)//> res4: List[Int] = List(0, 1, 2, 3, 4)`

`1 def zipIndex[A](xs: List[A]): List[(A, Int)] =2  xs.foldLeft(State.state[Int,List[(A,Int)]](List()))(3 (acc, a) => for {4 xn <- acc5 n <- get[Int]6 _ <- put[Int](n+1)7 } yield (a,n) :: xn).evalZero.reverse //> zipIndex: [A](xs: List[A])List[(A, Int)]89 zipIndex(1 |-> 5) //> res5: List[(Int, Int)] = List((1,0), (2,1), (3,2), (4,3), (5,4))`

` 1 def zipIndex[A](xs: List[A]): List[(A, Int)] = 2  xs.foldLeft(State.state[Int,List[(A,Int)]](List()))( 3 (acc, a) => for { 4 xn <- acc 5 n <- get[Int] 6 _ <- put[Int](n+1) 7 } yield (a,n) :: xn).lift[Trampoline].evalZero.run.reverse.take(10) 8 //> zipIndex: [A](xs: List[A])List[(A, Int)] 910 zipIndex(1 |-> 1000) //> res5: List[(Int, Int)] = List((1,0), (2,1), (3,2), (4,3), (5,4), (6,5), (7,11 //| 6), (8,7), (9,8), (10,9))`

`object StateTUsage extends App {import StateT._def f[M[_]: Functor] {Functor[({type l[a] = StateT[M, Int, a]})#l]}def m[M[_]: Monad] {Applicative[({type l[a] = StateT[M, Int, a]})#l]Monad[({type l[a] = StateT[M, Int, a]})#l]MonadState[({type f[s, a] = StateT[M, s, a]})#f, Int]}def state() {val state: State[String, Int] = State((x: String) => (x + 1, 0))val eval: Int = state.eval("")state.flatMap(_ => state)}}`

` import Scalaz._import scala.language.higherKindsdef f[M[_]: Functor] {Functor[({type l[a] = StateT[M, Int, a]})#l]} //> f: [M[_]](implicit evidence\$2: scalaz.Functor[M])Unitdef m[M[_]: Monad] {Applicative[({type l[a] = StateT[M, Int, a]})#l]Monad[({type l[a] = StateT[M, Int, a]})#l]MonadState[({type f[s, a] = StateT[M, s, a]})#f, Int]} //> m: [M[_]](implicit evidence\$3: scalaz.Monad[M])Unitdef state() {val state: State[String, Int] = State((x: String) => (x + 1, 0))val eval: Int = state.eval("")state.flatMap(_ => state)} //> state: ()Unitf[List]m[List]state`

` 1 //Functor实例 2 val fs = Functor[({type l[a] = StateT[List, Int, a]})#l] 3 //> fs : scalaz.Functor[[a]scalaz.IndexedStateT[[+A]List[A],Int,Int,a]] = scala 4 //| [email protected] 5 State[Int,Int] {s => (s+1,s)} //> res0: scalaz.State[Int,Int] = [email protected] 6 val st = StateT[List, Int, Int](s => List((s,s)))//> st : scalaz.StateT[List,Int,Int] = [email protected] 7 fs.map(st){a => a + 1}.run(0) //> res1: List[(Int, Int)] = List((0,1)) 8 //MonadState实例 9 val ms = MonadState[({type f[s, a] = StateT[List, s, a]})#f, Int]10 //> ms : scalaz.MonadState[[s, a]scalaz.IndexedStateT[[+A]List[A],s,s,a],Int] =11 //| [email protected]12 ms.state(1).run(0) //> res2: List[(Int, Int)] = List((0,1))13 //Monad实例14 val monad = Monad[({type l[a] = StateT[List, Int, a]})#l]15 //> monad : scalaz.Monad[[a]scalaz.IndexedStateT[[+A]List[A],Int,Int,a]] = scal16 //| [email protected]17 monad.bind(st){a => StateT(a1 => List((a1,a)))}.run(0)18 //Applicative实例 //> res3: List[(Int, Int)] = List((0,0))19 val ap = Applicative[({type l[a] = StateT[List, Int, a]})#l]20 //> ap : scalaz.Applicative[[a]scalaz.IndexedStateT[[+A]List[A],Int,Int,a]] = s21 //| [email protected]22 ap.point(0).run(0) //> res4: List[(Int, Int)] = List((0,0))`

`1 // def state() {2 //构建一个State实例。每次它的状态会加个!符号3 val state: State[String, Int] = State((x: String) => (x + "!", 0))4 //> state : scalaz.State[String,Int] = [email protected]5 //运算值不变6 val eval: Int = state.eval("") //> eval : Int = 07 //连续两次运行状态运算函数。加两个!8 state.flatMap(_ => state).run("haha") //> res0: scalaz.Id.Id[(String, Int)] = (haha!!,0)9 // }`

`trait Cachetrait FollowerStatedef followerState(user: String, cache: Cache): (Cache, FollowerState) = {val (c1,ofs) = checkCache(user,cache) //检查cache里有没有user资料//c1是新cache,更新了hit或miss countofs match { //在cache里找到否case Some(fs) => (c1,fs) //找到就返回fs和新cache c1case None => retrieve(user,c1) //找不到就从数据库里重新读取 }}//检查cache，更新cache hit/miss countdef checkCache(user: String, cache: Cache): (Cache, Option[FollowerState]) = ...//从数据库读取user资料，更新加入cachedef retrieve(user: String, cache: Cache): (Cache, FollowerState) = ...`

`def followerState(user: String, cache: Cache): (Cache, FollowerState)def followerState(user: String)(cache: Cache): (Cache, FollowerState)def followerState(user: String): Cache => (Cache, FollowerState)`

`def checkCache(user: String): Cache => (Cache, Option[FollowerState]) = ...def retrieve(user: String): Cache => (Cache, FollowerState) = ...`

`def followerState(user: String): Cache => (Cache, FollowerState) = cache => {val (c1,ofs) = checkCache(user,cache)ofs match {case Some(fs) => (c1,fs)case None => retrieve(user,c1)}}`

`def followerState(user: String): State[Cache,FollowerState] = State {cache => {val (c1,ofs) = checkCache(user,cache)ofs match {case Some(fs) => (c1,fs)case None => retrieve(user,c1)}}}`

`def checkCache(user: String): State[Cache,Option[FollowerState]] = ...def retrieve(user: String): State[Cache,FollowerState] = ...`

`def followerState(user: String): State[Cache,FollowerState] = for {optfs <- checkCache(user)fs <- optfs match {case Some(fs) => State{ s => (s, fs) }case None => retrieve(user)}} yield fs`

`followerState("Johny Depp").eval(emptyCache)`