在前面几次讨论中我们介绍了Free是个产生Monad的最基本结构。它的原理是把一段程序（AST）一连串的运算指令（ADT）转化成数据结构存放在内存里，这个过程是个独立的功能描述过程。然后另一个独立运算过程的Interpreter会遍历（traverse）AST结构，读取结构里的运算指令，实际运行指令。这里的重点是把一连串运算结构化（reify）延迟运行，具体实现方式是把Monad的连续运算方法flatMap转化成一串Suspend结构（case class），把运算过程转化成创建（construct）Suspend过程。flatMap的表现形式是这样的：flatMap(a => flatMap(b => flatMap(c => ....)))，这是是明显的递归算法，很容易产生堆栈溢出异常（StackOverflow Exception）,无法保证程序的安全运行，如果不能有效解决则FP编程不可行。Free正是解决这个问题的有效方法，因为它把Monad的递归算法flatMap转化成了一个创建数据结构实例的过程。每创建一个Suspend，立即完成一个运算。我们先用个例子来证明Monad flatMap的递归算法问题：
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 <- acc 5 s <- get[Int] 6 _ <- put[Int](s+1) 7 } yield ((s,a) :: xn) 8 ).eva l(1).reverse //> zipIndex: [A](xa: List[A])List[(Int, A)]
9
10 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
在这个例子里我们使用了State Monad。我们知道for-comprehension就是flatMap链条，是一种递归算法，所以当zipIndex针对大List时就产生了StackOverflowError。
我们提到过用Trampoline可以heap换stack，以遍历数据结构代替递归运算来实现运行安全。那么什么是Trampoline呢？
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 => true
4 case h :: t => isOdd(t) 5 } //> isEven: (xa: List[Int])Boolean
6 def isOdd(xa: List[Int]): Boolean =
7 xa match { 8 case Nil => false
9 case h :: t => isEven(t) 10 } //> isOdd: (xa: List[Int])Boolean
11
12 isOdd(0 |-> 100) //> res0: Boolean = true
13 isEven(0 |-> 10000) //> java.lang.StackOverflowError
可以看到isEven和isOdd这两个函数相互递归调用，最终用大点的List就产生了StackOverflowError。
现在重新调整一下函数isEven和isOdd的返回结构类型：从Boolean换成Trampoline，意思是从返回一个结果值变成返回一个数据结构：
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]
11
12 even(1 |-> 123001) //> res0: Exercises.trampoline.Trampoline[Boolean] = More(<function0>)
现在我们获得了一个在heap上存放了123001个元素的数据结构More(<function0>)。这是一个在内存heap上存放的过程，并没有任何实质运算。
现在我们需要一个方法来遍历这个返回的结构，逐个运行结构中的function0：
1 sealed trait Trampoline[+A] { 2 final def runT: A =
3 this match { 4 case Done(a) => a 5 case More(k) => k().runT 6 } 7 } 8
9 even(1 |-> 123001).runT //> res0: Boolean = false
由于这个runT是个尾递归（Tail Call Elimination TCE）算法，所以没有出现StackOverflowError。
实际上scalaz也提供了Trampoline类型：scalaz/Free.scala
/** 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