# Scalaz（34）－ Free ：算法－Interpretation

` /** 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)})`

` 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 methods15 def askNumber(q: String) = Question(q, (inputString => inputString.toInt)) //_.toInt16 def askOperator(q: String) = Question(q, (inputString => inputString.head.toUpper.toChar)) //_.head.toUpper.toChar17 def answer(fnum: Int, snum: Int, opr: Char) = {18 def result =19 opr match {20 case 'A' => fnum + snum21 case 'M' => fnum * snum22 case 'D' => fnum / snum23 case 'S' => fnum - snum24 }25 Answer("my answer is: " + result.toString,())26 }27 implicit def quizToFree[A](qz: Quiz[A]): Free[Quiz,A] = Free.liftF(qz)28 }29 import Quiz._30 val prg = for {31 fn <- askNumber("The first number is:")32 sn <- askNumber("The second number is:")33 op <- askOperator("The operation is:")34 _ <- answer(fn,sn,op)35 } yield() `

`1 def runQuiz[A](p: Free[Quiz,A]): Unit= p.fold(_ => (), {2 case Question(q,f) => {3 println(q)4 runQuiz(f(readLine))5 }6 case Answer(a,n) => println(a)7 }) `

`1 object main extends App {2 import freeRun._3 import qz._4 runQuiz(prg)5 }`

`The first number is:3The second number is:8The operation is:mulmy answer is: 24`

` 1 object QuizConsole extends (Quiz ~> Id) {2 import Quiz._3 def apply[A](qz: Quiz[A]): Id[A] = qz match {4 case Question(a,f) => {5 println(a)6 f(readLine)7 }8 case Answer(a,n) => println(a);n9 }10 }11 //运行foldMap12 prg.foldMap(QuizConsole)13 //结果一致`

` 1 type Tester[A] = Map[String, String] => (List[String], A)2 object QuizTester extends (Quiz ~> Tester) {3 def apply[A](qa: Quiz[A]): Tester[A] = qa match {4 case Question(q,f) => m => (List(),f(m(q)))5 case Answer(a,n) => m => (List(a),n)6 }7 }8 implicit object testerMonad extends Monad[Tester] {9 def point[A](a: => A) = _ => (List(),a)10 def bind[A,B](ta: Tester[A])(f: A => Tester[B]): Tester[B] =11 m => {12 val (o1,a) = ta(m)13 val (o2,b) = f(a)(m)14 (o1 ++ o2, b)15 }16 }`

`1 val m = Map(2 "The first number is:" -> "8",3 "The second number is:" -> "3",4 "The operation is:" -> "Sub"5 )6 println(prg.foldMap(QuizTester).apply(m))7 //(List(my answer is: 5),())`

foldRun通过入参数f:(B,S[Free[S,A]])=>(B,Free[S,A])支持状态跟踪,入参数b:B是状态初始值。我们先实现这个f函数：

` 1 type FreeQuiz[A] = Free[Quiz,A]2 def quizst(track: List[String], prg: Quiz[FreeQuiz[Unit]]): (List[String], FreeQuiz[Unit]) =3 prg match {4 case Question(q,f) => {5 println(q)6 val input = readLine7 (q+input :: track, f(input))8 }9 case Answer(a,n) => println(a); (a :: track, n)10 }`

`println(prg.foldRun(List[String]())(quizst)._1)The first number is:2The second number is:4The operation is:Mulmy answer is: 8List(my answer is: 8, The operation is:Mul, The second number is:4, The first number is:2)`

`1 type FreeQuiz[A] = Free[Quiz,A]2 def runquiz[A](prg: Quiz[FreeQuiz[A]]): Id[FreeQuiz[A]] =3 prg match {4 case Question(q,f) => {5 println(q)6 f(readLine)7 }8 case Answer(a,n) => println(a); n9 }`

`prg.runM(run quiz)The first number is:4The second number is:2The operation is:Mulmy answer is: 8`

` 1 sealed trait Calc[+A]2 object Calc {3 case class Push(value: Int) extends Calc[Unit]4 case class Add() extends Calc[Unit]5 case class Mul() extends Calc[Unit]6 case class Div() extends Calc[Unit]7 case class Sub() extends Calc[Unit]8 implicit def calcToFree[A](ca: Calc[A]) = Free.liftFC(ca)9 }10 import Calc._11 val ast = for {12 _ <- Push(23)13 _ <- Push(3)14 _ <- Add()15 _ <- Push(5)16 _ <- Mul()17 } yield () //> ast : scalaz.Free[[x]scalaz.Coyoneda[Exercises.interact.Calc,x],Unit] = Gosub()`

`/** A free monad over the free functor generated by `S` */type FreeC[S[_], A] = Free[({type f[x] = Coyoneda[S, x]})#f, A]}`

` 1 type Stack = List[Int]2 type StackState[A] = State[Stack,A]3 object CalcStack extends (Calc ~> StackState) {4 def apply[A](ca: Calc[A]): StackState[A] = ca match {5 case Push(v) => State((s: Stack) => (v :: s, ()))6 case Add() => State((s: Stack) => {7 val a :: b :: t = s8 ((a+b) :: t,())9 })10 case Mul() => State((s: Stack) => {11 val a :: b :: t = s12 ((a * b) :: t, ())13 })14 case Div() => State((s: Stack) => {15 val a :: b :: t = s16 ((a / b) :: t,())17 })18 case Sub() => State((s: Stack) => {19 val a :: b :: t = s20 ((a - b) :: s, ())21 })22 }23 }`

`println(Free.runFC(ast)(CalcStack).apply(List[Int]()))//(List(130),())`