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)

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) = {

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 }

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)

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:

3

The second number is:

8

The operation is:

mul

my 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)

7 }

8 case Answer(a,n) => println(a);n

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 }

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 = readLine

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

my answer is: 8

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

my 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 = 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),())

Top