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

```1 def foldR[A,B](as: List[A], b: B, f: (A,B) => B): B = as match {
2     case Nil => b
3     case h :: t => f(h,foldR(t,b,f))
4 }                                                 //> foldR: [A, B](as: List[A], b: B, f: (A, B) => B)B
5 def add(a: Int, b: Int) = a + b                   //> add: (a: Int, b: Int)Int
6
7 foldR((1 to 100).toList, 0, add)                  //> res0: Int = 5050
8 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 => b
3     case h :: t => foldL(t,f(b,h),f)
4 }                                                 //> foldL: [A, B](as: List[A], b: B, f: (B, A) => B)B
5 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 = xs
11         }
12       }
13     }
14     z
15   }```

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

```1 even((1 to 100).toList)                           //> res2: Boolean = true
2 even((1 to 101).toList)                           //> res3: Boolean = false
3 odd((1 to 100).toList)                            //> res4: Boolean = false
4 odd((1 to 101).toList)                            //> res5: Boolean = true
5 even((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 }
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 = true
2 even((1 to 10001).toList).runT                    //> res7: Boolean = false
3 odd((1 to 10000).toList).runT                     //> res8: Boolean = false
4 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.reverse
10 }                                                 //> 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,6
2                                                   //| ), (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) => a
18       case More(k) => k().runT
19   }
20 }
21 case class Done[+A](a: A) extends Trampoline[A]
22 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]
23
24 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 <- acc
29         n <- getState[Int]
30         _ <- setState[Int](n + 1)
31       } yield (a,n) :: xs
32     ).runS(0).runT._1.reverse
33 }                                                 //> 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).resume
20         case More(k) => Left(() => k() flatMap f)
21         case FlatMap(b,g) => FlatMap(b, (x: Any) => g(x) flatMap f).resume
22     }
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.reverse
10 }                                                 //> 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
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 + y
6 }                                                 //> 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).resume
20         case More(k) => Left(() => k() flatMap f)
21         case FlatMap(b,g) => FlatMap(b, (x: Any) => g(x) flatMap f).resume
22     }
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]
5
6 (hello zip hello zip hello).runT                  //> Hello Hello Hello World!
7                                                   //| World!
8                                                   //| World!
9                                                   //| res8: ((Unit, Unit), Unit) = (((),()),())```

0 条评论

## 相关文章

### 编程小技巧

1.判断一个自然数是否是某个数的平方？（其实就是判断这个数一定是奇数相加的） 由于 (n+1)^2 =n^2 + 2n + 1， = ... = 1 +...

21110

2096

1022

### Codeforce 712A Memory and Crow

A. Memory and Crow time limit per test:2 seconds memory limit per test:256 megab...

3066

### Kotlin 函数编程详解函数Kotlin 开发者社区

Functions in Kotlin are declared using the fun keyword:

683

### ZOJ 3605 Find the Marble（dp）

Find the Marble ---- Time Limit: 2 Seconds      Memory Limit: 65536 KB ---- Alic...

3647

### 泛函编程（10）－异常处理－Either

上节我们介绍了新的数据类型Option：一个专门对付异常情况出现时可以有一致反应所使用的数据类型。Option可以使编程人员不必理会出现异常后应该如何...

1925

35511