# 泛函编程（29）－泛函实用结构：Trampoline-不再怕StackOverflow

`1 def foldR[A,B](as: List[A], b: B, f: (A,B) => B): B = as match {2 case Nil => b3 case h :: t => f(h,foldR(t,b,f))4 } //> foldR: [A, B](as: List[A], b: B, f: (A, B) => B)B5 def add(a: Int, b: Int) = a + b //> add: (a: Int, b: Int)Int67 foldR((1 to 100).toList, 0, add) //> res0: Int = 50508 foldR((1 to 10000).toList, 0, add) //> java.lang.StackOverflowError`

`1 def foldL[A,B](as: List[A], b: B, f: (B,A) => B): B = as match {2 case Nil => b3 case h :: t => foldL(t,f(b,h),f)4 } //> foldL: [A, B](as: List[A], b: B, f: (B, A) => B)B5 foldL((1 to 100000).toList, 0, add) //> res1: Int = 705082704`

` 1  def foldl2[A,B](as: List[A], b: B, 2 f: (B,A) => B): B = { 3 var z = b 4 var az = as 5 while (true) { 6  az match { 7 case Nil => return z 8 case x :: xs => { 9 z = f(z, x)10 az = xs11  }12  }13  }14  z15 }`

`1 def even[A](as: List[A]): Boolean = as match {2 case Nil => true3 case h :: t => odd(t)4 } //> even: [A](as: List[A])Boolean5 def odd[A](as: List[A]): Boolean = as match {6 case Nil => false7 case h :: t => even(t)8 } //> odd: [A](as: List[A])Boolean`

`1 even((1 to 100).toList) //> res2: Boolean = true2 even((1 to 101).toList) //> res3: Boolean = false3 odd((1 to 100).toList) //> res4: Boolean = false4 odd((1 to 101).toList) //> res5: Boolean = true5 even((1 to 10000).toList) //> java.lang.StackOverflowError`

`1 trait Trampoline[+A] {2 final def runT: A = this match {3 case Done(a) => a4 case More(k) => k().runT5  }6 }7 case class Done[+A](a: A) extends Trampoline[A]8 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]`

Trampoline代表一个可以一步步进行的运算。每步运算都有两种可能：Done(a),直接完成运算并返回结果a，或者More(k)运算k后进入下一步运算；下一步又有可能存在Done和More两种情况。注意Trampoline的runT方法是明显的尾递归，而且runT有final标示，表示Scala可以进行TCE。

`1 def even[A](as: List[A]): Trampoline[Boolean] = as match {2 case Nil => Done(true)3 case h :: t => More(() => odd(t))4 } //> even: [A](as: List[A])ch13.ex1.Trampoline[Boolean]5 def odd[A](as: List[A]): Trampoline[Boolean] = as match {6 case Nil => Done(false)7 case h :: t => More(() => even(t))8 } //> odd: [A](as: List[A])ch13.ex1.Trampoline[Boolean]`

`1 even((1 to 10000).toList).runT //> res6: Boolean = true2 even((1 to 10001).toList).runT //> res7: Boolean = false3 odd((1 to 10000).toList).runT //> res8: Boolean = false4 odd((1 to 10001).toList).runT //> res9: Boolean = true`

` 1 case class State[S,+A](runS: S => (A,S)) { 2 import State._ 3 def flatMap[B](f: A => State[S,B]): State[S,B] = State[S,B] { 4 s => { 5 val (a1,s1) = runS(s) 6  f(a1) runS s1 7  } 8  } 9 def map[B](f: A => B): State[S,B] = flatMap( a => unit(f(a)))10 }11 object State {12 def unit[S,A](a: A) = State[S,A] { s => (a,s) }13 def getState[S]: State[S,S] = State[S,S] { s => (s,s) }14 def setState[S](s: S): State[S,Unit] = State[S,Unit] { _ => ((),s)}15 }`

` 1 def zip[A](as: List[A]): List[(A,Int)] = { 2  as.foldLeft( 3  unit[Int,List[(A,Int)]](List()))( 4 (acc,a) => for { 5 xs <- acc 6 n <- getState[Int] 7 _ <- setState[Int](n + 1) 8  } yield (a,n) :: xs 9 ).runS(0)._1.reverse10 } //> zip: [A](as: List[A])List[(A, Int)]`

`1 zip((1 to 10).toList) //> res0: List[(Int, Int)] = List((1,0), (2,1), (3,2), (4,3), (5,4), (6,5), (7,62 //| ), (8,7), (9,8), (10,9))`

`1 zip((1 to 10000).toList) //> java.lang.StackOverflowError`

` 1 case class State[S,A](runS: S => Trampoline[(A,S)]) { 2 def flatMap[B](f: A => State[S,B]): State[S,B] = State[S,B] { 3 s => More(() => { 4 val (a1,s1) = runS(s).runT 5 More(() => f(a1) runS s1) 6  }) 7  } 8 def map[B](f: A => B): State[S,B] = flatMap( a => unit(f(a))) 9 }10 object State {11 def unit[S,A](a: A) = State[S,A] { s => Done((a,s)) }12 def getState[S]: State[S,S] = State[S,S] { s => Done((s,s)) }13 def setState[S](s: S): State[S,Unit] = State[S,Unit] { _ => Done(((),s))}14 }15 trait Trampoline[+A] {16 final def runT: A = this match {17 case Done(a) => a18 case More(k) => k().runT19  }20 }21 case class Done[+A](a: A) extends Trampoline[A]22 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]2324 def zip[A](as: List[A]): List[(A,Int)] = {25  as.foldLeft(26  unit[Int,List[(A,Int)]](List()))(27 (acc,a) => for {28 xs <- acc29 n <- getState[Int]30 _ <- setState[Int](n + 1)31  } yield (a,n) :: xs32 ).runS(0).runT._1.reverse33 } //> zip: [A](as: List[A])List[(A, Int)]34 zip((1 to 10).toList) //> res0: List[(Int, Int)] = List((1,0), (2,1), (3,2), (4,3), (5,4), (6,5), (7,35 //| 6), (8,7), (9,8), (10,9))`

`1 zip((1 to 10000).toList) //> java.lang.StackOverflowError`

` 1 trait Trampoline[+A] { 2 final def runT: A = this match { 3 case Done(a) => a 4 case More(k) => k().runT 5  } 6 def flatMap[B](f: A => Trampoline[B]): Trampoline[B] = { 7 this match { 8 case Done(a) => f(a) 9 case More(k) => f(runT)10  }11  }12 }13 case class Done[+A](a: A) extends Trampoline[A]14 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]`

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

`1 case class Done[+A](a: A) extends Trampoline[A]2 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]3 case class FlatMap[A,B](sub: Trampoline[A], k: A => Trampoline[B]) extends Trampoline[B]`

case class FlatMap这种Trampoline状态意思是先引用sub然后把结果传递到下一步k再运行k：基本上是沿袭flatMap功能。再调整Trampoline.resume, Trampoline.flatMap把FlatMap这种状态考虑进去：

` 1 trait Trampoline[+A] { 2 final def runT: A = resume match { 3 case Right(a) => a 4 case Left(k) => k().runT 5  } 6 def flatMap[B](f: A => Trampoline[B]): Trampoline[B] = { 7 this match { 8 // case Done(a) => f(a) 9 // case More(k) => f(runT)10 case FlatMap(a,g) => FlatMap(a, (x: Any) => g(x) flatMap f)11 case x => FlatMap(x, f)12  }13  }14 def map[B](f: A => B) = flatMap(a => Done(f(a)))15 def resume: Either[() => Trampoline[A], A] = this match {16 case Done(a) => Right(a)17 case More(k) => Left(k)18 case FlatMap(a,f) => a match {19 case Done(v) => f(v).resume20 case More(k) => Left(() => k() flatMap f)21 case FlatMap(b,g) => FlatMap(b, (x: Any) => g(x) flatMap f).resume22  }23  }24 }25 case class Done[+A](a: A) extends Trampoline[A]26 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]27 case class FlatMap[A,B](sub: Trampoline[A], k: A => Trampoline[B]) extends Trampoline[B]`

FlatMap(FlatMap(b,g),f) == FlatMap(b,x => FlatMap(g(x),f)

` 1 def zip[A](as: List[A]): List[(A,Int)] = { 2  as.foldLeft( 3  unit[Int,List[(A,Int)]](List()))( 4 (acc,a) => for { 5 xs <- acc 6 n <- getState[Int] 7 _ <- setState[Int](n + 1) 8  } yield (a,n) :: xs 9 ).runS(0).runT._1.reverse10 } //> zip: [A](as: List[A])List[(A, Int)]11 zip((1 to 10000).toList) //> res0: List[(Int, Int)] = List((1,0), (2,1), (3,2), (4,3), (5,4), (6,5), (7,`

`1 val x = f()2 val y = g(x)3 h(y)4 //以上这三步函数引用可以写成:5 for {6 x <- f()7 y <- g(x)8 z <- h(y)9 } yield z`

` 1 implicit def step[A](a: => A): Trampoline[A] = { 2 More(() => Done(a)) 3 } //> step: [A](a: => A)ch13.ex1.Trampoline[A] 4 def getNum: Double = 3 //> getNum: => Double 5 def addOne(x: Double) = x + 1 //> addOne: (x: Double)Double 6 def timesTwo(x: Double) = x * 2 //> timesTwo: (x: Double)Double 7 (for { 8 x <- getNum 9 y <- addOne(x)10 z <- timesTwo(y)11 } yield z).runT //> res6: Double = 8.0`

`1 def fib(n: Int): Trampoline[Int] = {2 if (n <= 1) Done(n) else for {3 x <- More(() => fib(n-1))4 y <- More(() => fib(n-2))5 } yield x + y6 } //> fib: (n: Int)ch13.ex1.Trampoline[Int]7 (fib(10)).runT //> res7: Int = 55`

` 1 trait Trampoline[+A] { 2 final def runT: A = resume match { 3 case Right(a) => a 4 case Left(k) => k().runT 5  } 6 def flatMap[B](f: A => Trampoline[B]): Trampoline[B] = { 7 this match { 8 // case Done(a) => f(a) 9 // case More(k) => f(runT)10 case FlatMap(a,g) => FlatMap(a, (x: Any) => g(x) flatMap f)11 case x => FlatMap(x, f)12  }13  }14 def map[B](f: A => B) = flatMap(a => Done(f(a)))15 def resume: Either[() => Trampoline[A], A] = this match {16 case Done(a) => Right(a)17 case More(k) => Left(k)18 case FlatMap(a,f) => a match {19 case Done(v) => f(v).resume20 case More(k) => Left(() => k() flatMap f)21 case FlatMap(b,g) => FlatMap(b, (x: Any) => g(x) flatMap f).resume22  }23  }24 def zip[B](tb: Trampoline[B]): Trampoline[(A,B)] = {25 (this.resume, tb.resume) match {26 case (Right(a),Right(b)) => Done((a,b))27 case (Left(f),Left(g)) => More(() => f() zip g())28 case (Right(a),Left(k)) => More(() => Done(a) zip k())29 case (Left(k),Right(a)) => More(() => k() zip Done(a))30  }31  }32 }33 case class Done[+A](a: A) extends Trampoline[A]34 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]35 case class FlatMap[A,B](sub: Trampoline[A], k: A => Trampoline[B]) extends Trampoline[B]`

`1 def hello: Trampoline[Unit] = for {2 _ <- print("Hello ")3 _ <- println("World!")4 } yield () //> hello: => ch13.ex1.Trampoline[Unit]56 (hello zip hello zip hello).runT //> Hello Hello Hello World!7 //| World!8 //| World!9 //| res8: ((Unit, Unit), Unit) = (((),()),())`

Top