在上节我们介绍了Trampoline。它主要是为了解决堆栈溢出（StackOverflow）错误而设计的。Trampoline类型是一种数据结构，它的设计思路是以heap换stack：对应传统递归算法运行时在堆栈上寄存程序状态，用Trampoline进行递归算法时程序状态是保存在Trampoline的数据结构里的。数据结构是在heap上的，所以可以实现以heap换stack的效果。这种以数据结构代替函数调用来解决问题的方式又为泛函编程提供了更广阔的发展空间。

`1 def transfer(amount: Double, from: Account, to: Account, user: User,2 context: Authorization with Logger with ErrorHandler with Storage): Unit`

`1 def transfer(amount: Double, from: Account, to: Account, user: User）： List[Instruction]`

`1 trait Interact[A] //交互数据类型2 //提问，等待返回String类型答案3 case class Ask(prompt: String) extends Interact[String]4 //告知，没有返回结果5 case class Tell(msg: String) extends Interact[Unit]`

`1 val prg = List(Ask("What's your first name?"),2 Ask("What's your last name?"),3 Tell("Hello ??? ???"))`

`1 for {2 x <- Ask("What's your first name?")3 y <- Ask("What's your last name?")4 _ <- Tell(s"Hello \$y \$x!")5 } yield () `

`1 trait Free[F[_],A]2 case class Return[F[_],A](a: A) extends Free[F,A]3 case class Bind[F[_],I,A](a: F[I], f: I => Free[F,A]) extends Free[F,A]`

` 1 trait Free[F[_],A] { 2 def unit(a: A) = Return(a) 3 def flatMap[B](f: A => Free[F,B]): Free[F,B] = this match { 4 case Return(a) => f(a) 5 //还记得Trampoline FlatMap(FlatMap(b,g),f) == FlatMap(b, (x: Any) => FlatMap(g(x),f))  6 case Bind(fa,g) => Bind(fa, (x: Any) => g(x) flatMap f) 7 //下面采用了函数组合方式。具备同样功能 8 // case Bind(fa,g) => Bind(fa, g andThen (_ flatMap f)) 9  }10 def map[B](f: A => B): Free[F,B] = flatMap(a => Return(f(a)))1112 }13 case class Return[F[_],A](a: A) extends Free[F,A]14 case class Bind[F[_],I,A](a: F[I], f: I => Free[F,A]) extends Free[F,A]`

`1 implicit def lift[F[_],A](fa: F[A]): Free[F,A] = Bind(fa, (a: A) => Return(a))2 //> lift: [F[_], A](fa: F[A])ch13.ex6.Free[F,A]`

` 1 trait Interact[A] //交互数据类型 2 //提问，等待返回String类型答案 3 case class Ask(prompt: String) extends Interact[String] 4 //告知，没有返回结果 5 case class Tell(msg: String) extends Interact[Unit] 6 7 implicit def lift[F[_],A](fa: F[A]): Free[F,A] = Bind(fa, (a: A) => Return(a)) 8 //> lift: [F[_], A](fa: F[A])ch13.ex6.Free[F,A] 9 for {10 x <- Ask("What's your first name?")11 y <- Ask("What's your last name?")12 _ <- Tell(s"Hello \$y \$x!")13 } yield () //> res0: ch13.ex6.Free[ch13.ex6.Interact,Unit] = Bind(Ask(What's your first nam14 //| e?),<function1>)`

`1 trait ~>[F[_],G[_]] {2  def apply[A](fa: F[A]): G[A]3 }`

`1 def foldMap[G[_]: Monad](f: F ~> G): G[A] = this match {2 case Return(a) => Monad[G].unit(a)3 case Bind(b,g) => Monad[G].flatMap(f(b))(a => g(a).foldMap(f))4 }`

` 1 ype Id[A] = A 2 implicit val idMonad: Monad[Id] = new Monad[Id] { 3 def unit[A](a: A) = a 4 def flatMap[A,B](fa: A)(f: A => B): B = f(fa) 5 } //> idMonad : ch13.ex6.Monad[ch13.ex6.Id] = [email protected] 6 //| 530c12 7 object Console extends (Interact ~> Id) { 8 def apply[A](i: Interact[A]): A = i match { 9 case Ask(prompt) => {10  println(prompt)11  readLine12  }13 case Tell(msg) => println(msg)14  }15 }`

`1 val prg = for {2 x <- Ask("What's your first name?")3 y <- Ask("What's your last name?")4 _ <- Tell(s"Hello \$y \$x!")5 } yield () //> prg : ch13.ex6.Free[ch13.ex6.Interact,Unit] = Bind(Ask(What's your first n6 //| ame?),<function1>)78 prg.foldMap(Console)`

` 1 type Tester[A] = Map[String, String] => (List[String], A) 2 implicit val testerMonad = new Monad[Tester] { 3 def unit[A](a: A) = (_ => (List(),a)) 4 def flatMap[A,B](ta: Tester[A])(f: A => Tester[B]): Tester[B] = { 5 m => { 6 val (l1,a) = ta(m) 7 val (l2,b) = f(a)(m) 8 (l1 ++ l2,b) 9  }10  }11 } //> testerMonad : ch13.ex6.Monad[ch13.ex6.Tester]{def unit[A](a: A): Map[Strin12 //| g,String] => (List[Nothing], A)} = [email protected]13 //| 814 object TestConsole extends (Interact ~> Tester) {15 def apply[A](i: Interact[A]): Tester[A] = i match {16 case Ask(prompt) => m => (List(), m(prompt))17 case Tell(msg) => _ => (List(msg),())18  }19 }`

`1 val prg = for {2 x <- Ask("What's your first name?")3 y <- Ask("What's your last name?")4 _ <- Tell(s"Hello \$y \$x!")5 } yield () //> prg : ch13.ex6.Free[ch13.ex6.Interact,Unit] = Bind(Ask(What's your first n6 //| ame?),<function1>)78 prg.foldMap(TestConsole)`

Top