) //> res2: scalaz.Id.Id[(List[Int], Int)] = (List(9, 10),2)
实际上在StateT里已经实现了filter函数,可以看看下面的例子:
1 val prg1 = for { 2 _ <- push(1) 3 _ <- push(2) 4 _ <- push(3) 5 a <- pop 6 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] = scalaz.IndexedStateT$$anon$10@3349e9bb
9 prg1.run(List()) //> res4: scalaz.Id.Id[(List[Int], Unit)] = (List(1, 2, 3),())
因为StateT实现了MonadPlus实例:scalaz/StateT.scala
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))) }
当然,这个StateT的F必须是MonadPlus实例。liftM能把Monad生格成StateT:
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).eva lZero[Int] //> res3: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
从运算结果来看还是正常的。但如果我这样用:
incr.replicateM(10000).runZero[Int] //> java.lang.StackOverflowError
啊!StackOverflowError。解决堆栈溢出其中一个方法是使用Trampoline结构,以heap换stack。Trampoline就是Free Monad的一个特殊案例,我们后面会详细介绍Free Monad。现在可以用lift把F[(S2,A)]升格成M[F[(S2,A)]]:
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)) }
我们可以把State返回类型升格成为Trampoline,就像这样:
1 import scalaz.Free.Trampoline 2 incr.lift[Trampoline].replicateM(10).eva lZero[Int] 3 //> res4: scalaz.Free[Function0,List[Int]] = Gosub()
现在看看解决了StackOverflowError问题没有:
import scalaz.Free.Trampoline incr.lift[Trampoline].replicateM(10000).eva lZero[Int].run.take(5) //> res4: List[Int] = List(0, 1, 2, 3, 4)
问题解决。注意上面的表达式后面加多了一个run指令,这是因为现在返回的类型已经是Trampoline了。再看另外一个例子,我们用State在List里添加行号:
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).eva lZero.reverse //> zipIndex: [A](xs: List[A])List[(A, Int)]
8
9 zipIndex(1 |-> 5) //> res5: List[(Int, Int)] = List((1,0), (2,1), (3,2), (4,3), (5,4))
同样,我也可以把返回类型升格成Trampoline:
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].eva lZero.run.reverse.take(10) 8 //> zipIndex: [A](xs: List[A])List[(A, Int)]
9
10 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))
看起来可以升格到Trampoline,但实际上还没有解决StackOverflowError问题。这个细节就留在后面我们讨论Free Monad时再研究吧。
作为一种惯例,我们还是看看scalaz提供的用例有什么值得注意的:scalaz-example/StateTUsage.scala
object StateTUsage extends App { import StateT._ def f[M[_]: Functor] { Functor[({type l[a] = S |