# 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 {
}

/** 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 {
}
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)
12       }
13   }
14 //操作帮助方法helper methods
15   def askNumber(q: String) = Question(q, (inputString => inputString.toInt))  //_.toInt
17   def answer(fnum: Int, snum: Int, opr: Char) = {
18     def result =
19       opr match {
20         case 'A' => fnum + snum
21         case 'M' => fnum * snum
22         case 'D' => fnum / snum
23         case 'S' => fnum - snum
24       }
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:")
35 } yield()       ```

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

```1 object main extends App {
2 import freeRun._
3 import qz._
4 runQuiz(prg)
5 }```

```The first number is:
3
The second number is:
8
The operation is:
mul

``` 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)
7     }
9   }
10 }
11 //运行foldMap
12 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 }
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))

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)
7       (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:
2
The second number is:
4
The operation is:
Mul
List(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)
7   }
8   case Answer(a,n) => println(a); n
9 }```

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

``` 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)
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 = s
8       ((a+b) :: t,())
9     })
10     case Mul() => State((s: Stack) => {
11       val a :: b :: t = s
12       ((a * b) :: t, ())
13     })
14     case Div() => State((s: Stack) => {
15       val a :: b :: t = s
16       ((a / b) :: t,())
17     })
18     case Sub() => State((s: Stack) => {
19       val a :: b :: t = s
20       ((a - b) :: s, ())
21     })
22   }
23 }```

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

0 条评论

## 相关文章

1150

941

4776

722

### Codeforce 712A Memory and Crow

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

3076

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

Functions in Kotlin are declared using the fun keyword:

683

### json转成java对象

avro生成的代码里，String是CharSequence，不能通过Gson反序列化，于是有了下面的代码，ParseArray里还不完善： 1 static...

3637

### 赋值运算符函数__from <剑指Offer>

前段时间忙于项目，难得偷得几日闲，为即将到来的就业季做准备。在面试时，应聘者要注意多和考官交流，只有具备良好的沟通能力，才能充分了解面试官的需求...

2725

### HDU 5677 ztr loves substring（回文串加多重背包）

ztr loves substring Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 655...

3474