我们说过自由数据结构（free structures）是表达数据类型的最简单结构。List[A]是个数据结构，它是生成A类型Monoid的最简单结构，因为我们可以用List的状态cons和Nil来分别代表Monoid的append和zero。Free[S,A]是个代表Monad的最简单数据结构，它可以把任何Functor S升格成Monad。Free的两个结构Suspend,Return分别代表了Monad的基本操作函数flatMap,point，我特别强调结构的意思是希望大家能意识到那就是内存heap上的一块空间。我们同样可以简单的把Functor视为一种算法，通过它的map函数实现运算。我们现在可以把Monad的算法flatMap用Suspend[S[Free[S,A]]来表示，那么一段由Functor S（ADT）形成的程序（AST）可以用一串递归结构表达：Suspend(S(Suspend(S(Suspend(S(....(Return)))))))。我们可以把这样的AST看成是一串链接的内存格，每个格内存放着一个算法ADT，代表下一个运算步骤，每个格子指向下一个形成一串连续的算法，组成了一个完整的程序（AST）。最明显的分别是Free把Monad flatMap这种递归算法化解成内存数据结构，用内存地址指向代替了递归算法必须的内存堆栈（stack）。Free的Interpretation就是对存放在数据结构Suspend内的算法（ADT）进行实际运算。不同方式的Interpreter决定了这段由一连串ADT形成的AST的具体效果。
Free Interpreter的具体功能就是按存放在数据结构Suspend内的算法（ADT）进行运算后最终获取A值。这些算法的实际运算可能会产生副作用，比如IO算法的具体操作。scalaz是通过几个运算函数来提供Free Interpreter，包括：fold,foldMap,foldRun,runFC,runM。我们先看看这几个函数的源代码：
/** Catamorphism. Run the first given function if Return, otherwise, the second given function. */ final def fold[B](r: A => B, s: S[Free[S, A]] => B)(implicit S: Functor[S]): B = resume.fold(s, r) /** * Catamorphism for `Free`. * Runs to completion, mapping the suspension with the given transformation at each step and * accumulating into the monad `M`. */ final def foldMap[M[_]](f: S ~> M)(implicit S: Functor[S], M: Monad[M]): M[A] =
this.resume match { case -\/(s) => Monad[M].bind(f(s))(_.foldMap(f)) case \/-(r) => Monad[M].pure(r) } /** Runs to completion, allowing the resumption function to thread an arbitrary state of type `B`. */ final def foldRun[B](b: B)(f: (B, S[Free[S, A]]) => (B, Free[S, A]))(implicit S: Functor[S]): (B, A) = { @tailrec def foldRun2(t: Free[S, A], z: B): (B, A) = t.resume match { case -\/(s) => val (b1, s1) = f(z, s) foldRun2(s1, b1) case \/-(r) => (z, r) } foldRun2(this, b) } /** * Runs to completion, using a function that maps the resumption from `S` to a monad `M`. * @since 7.0.1 */ final def runM[M[_]](f: S[Free[S, A]] => M[Free[S, A]])(implicit S: Functor[S], M: Monad[M]): M[A] = { def runM2(t: Free[S, A]): M[A] = t.resume match { case -\/(s) => Monad[M].bind(f(s))(runM2) case \/-(r) => Monad[M].pure(r) } runM2(this) } /** Interpret a free monad over a free functor of `S` via natural transformation to monad `M`. */ def runFC[S[_], M[_], A](sa: FreeC[S, A])(interp: S ~> M)(implicit M: Monad[M]): M[A] = sa.foldMap[M](new (({type λ[α] = Coyoneda[S, α]})#λ ~> M) { def apply[A](cy: Coyoneda[S, A]): M[A] = M.map(interp(cy.fi))(cy.k) })
我们应该可以看出Interpreter的基本原理就是把不可运算的抽象指令ADT转换成可运算的表达式。在这个转换过程中产生运算结果。我们下面用具体例子一个一个介绍这几个函数的用法。还是用上期的例子：
1 object qz { 2 sealed trait Quiz[+Next] 3 object Quiz { 4 //问题que:String, 等待String 然后转成数字或操作符号
5 case class Question[Next](que: String, n: String => Next) extends Quiz[Next] 6 case class Answer[Next](ans: String, n: Next) extends Quiz[Next] 7 implicit object QFunctor extends Functor[Quiz] { 8 def map[A,B](qa: Quiz[A])(f: A => B): Quiz[B] =
9 qa match { 10 case q: Question[A] => Question(q.que, q.n andThen f) 11 case Answer(a,n) => Answer(a,f(n)) 12 } 13 } 14 //操作帮助方法helper methods
15 def askNumber(q: String) = Question(q, (inputString => inputString.toInt)) //_.toInt
16 def askOperator(q: String) = Question(q, (inputString => inputString.head.toUpper.toChar)) //_.head.toUpper.toChar
17 def answer(fnum: Int, snum: Int, opr: Char) =