# Scalaz（35）－ Free ：运算－Trampoline，say NO to StackOverflowError

` 1 ef zipIndex[A](xa: List[A]): List[(Int,A)] =2 xa.foldLeft(State.state[Int,List[(Int,A)]](List()))(3 (acc,a) => for {4 xn <- acc5 s <- get[Int]6 _ <- put[Int](s+1)7 } yield ((s,a) :: xn)8 ).eval(1).reverse //> zipIndex: [A](xa: List[A])List[(Int, A)]910 zipIndex(1 |-> 10) //> res6: List[(Int, Int)] = List((1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9), (10,10))11 zipIndex(1 |-> 10000) //> java.lang.StackOverflowError`

`1 sealed trait Trampoline[+A]2 case class Done[A](a: A) extends Trampoline[A]3 case class More[A](k: () => Trampoline[A]) extends Trampoline[A]`

Trampoline就是一种数据结构。它有两种状态：Done(a: A)代表结构内存放了一个A值，More(k: ()=>Trampoline[A])代表结构内存放的是一个Function0函数，就是一个运算Trampoline[A]。

` 1 def isEven(xa: List[Int]): Boolean =2 xa match {3 case Nil => true4 case h :: t => isOdd(t)5 } //> isEven: (xa: List[Int])Boolean6 def isOdd(xa: List[Int]): Boolean =7 xa match {8 case Nil => false9 case h :: t => isEven(t)10 } //> isOdd: (xa: List[Int])Boolean1112 isOdd(0 |-> 100) //> res0: Boolean = true13 isEven(0 |-> 10000) //> java.lang.StackOverflowError`

` 1 def even(xa: List[Int]): Trampoline[Boolean] =2 xa match {3 case Nil => Done(true)4 case h :: t => More(() => odd(t))5 } //> even: (xa: List[Int])Exercises.trampoline.Trampoline[Boolean]6 def odd(xa: List[Int]): Trampoline[Boolean] =7 xa match {8 case Nil => Done(false)9 case h :: t => More(() => even(t))10 } //> odd: (xa: List[Int])Exercises.trampoline.Trampoline[Boolean]1112 even(1 |-> 123001) //> res0: Exercises.trampoline.Trampoline[Boolean] = More(<function0>)`

`1 sealed trait Trampoline[+A] {2 final def runT: A =3 this match {4 case Done(a) => a5 case More(k) => k().runT6 }7 }89 even(1 |-> 123001).runT //> res0: Boolean = false`

` /** A computation that can be stepped through, suspended, and paused */type Trampoline[A] = Free[Function0, A]...object Trampoline extends TrampolineInstances {def done[A](a: A): Trampoline[A] =Free.Return[Function0,A](a)def delay[A](a: => A): Trampoline[A] =suspend(done(a))def suspend[A](a: => Trampoline[A]): Trampoline[A] =Free.Suspend[Function0, A](() => a)}`

` 1 import scalaz.Free.Trampoline2 def even(xa: List[Int]): Trampoline[Boolean] =3 xa match {4 case Nil => Trampoline.done(true)5 case h :: t => Trampoline.suspend(odd(t))6 } //> even: (xa: List[Int])scalaz.Free.Trampoline[Boolean]7 def odd(xa: List[Int]): Trampoline[Boolean] =8 xa match {9 case Nil => Trampoline.done(false)10 case h :: t => Trampoline.suspend(even(t))11 } //> odd: (xa: List[Int])scalaz.Free.Trampoline[Boolean]1213 even(1 |-> 123001).run //> res0: Boolean = false`

` 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 def incr: State[Int, Int] = State {s => (s+1, s)}//> incr: => scalaz.State[Int,Int]2 incr.replicateM(10000).eval(0) take 10 //> java.lang.StackOverflowError34 import scalaz.Free.Trampoline5 incr.lift[Trampoline].replicateM(100000).eval(0).run.take(10)6 //> res0: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)`

` 1 def safeZipIndex[A](xa: List[A]): List[(Int,A)] =2 (xa.foldLeft(State.state[Int,List[(Int,A)]](List()))(3 (acc,a) => for {4 xn <- acc5 s <- get[Int]6 _ <- put(s + 1)7 } yield (s,a) :: xn8 ).lift[Trampoline]).eval(1).run.reverse //> safeZipIndex: [A](xa: List[A])List[(Int, A)]910 safeZipIndex(1 |-> 1000).take(10) //> res2: List[(Int, Int)] = List((1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9), (10,10))`

`1 safeZipIndex(1 |-> 10000).take(10) //> java.lang.StackOverflowError2 //| at scalaz.IndexedStateT\$\$anonfun\$flatMap\$1.apply(StateT.scala:62)3 //| at scalaz.IndexedStateT\$\$anon\$10.apply(StateT.scala:95)4 //| at scalaz.IndexedStateT\$\$anonfun\$flatMap\$1.apply(StateT.scala:62)5 ...6 `

Top