Scalaz(34)- Free :算法-Interpretation

我们说过自由数据结构(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) = {
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()       

prg是一段功能描述:在提示后读取一个数字,重复一次,再读取一个字串,把读取的数字和字串用来做个运算。至于怎么提示、如何读取输入、如何运算输入内容,可能会有种种不同的方式,那要看Interpreter具体是怎么做的了。好了,现在我们看看如何用fold来运算prg:fold需要两个入参数:r:A=>B,一个在运算终止Return状态时运行的函数,另一个是s:S[Free[S,A]]=>B,这个函数在Suspend状态时运算入参数ADT:

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

注意runQuiz是个递归函数。在Suspend Question状态下,运算f(readLine)产生下一个运算。在这个函数里我们赋予了提示、读取正真的意义,它们都是通过IO操作println,readLine实现的。

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

结果正是我们期待的。但这个fold方法每调用一次只运算一个ADT,所以使用了递归算法连续约化Suspend直到Return。递归算法很容易造成堆栈溢出异常,不安全。下一个试试foldMap。foldMap使用了Monad.bind连续通过高阶类型转换(natural transformation)将ADT转换成运行指令,并在转换过程中实施运算:

 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);n
 9   }
10 }
11 //运行foldMap
12 prg.foldMap(QuizConsole)
13 //结果一致

上面的natural transformation是把Quiz类型转成Id类型。Id[A]=A,所以高阶类型Quiz可以被转换成基本类型Unit(println返回Unit)。这个例子同样用IO函数来实现AST功能。我们也可以用一个模拟的输入输出方式来测试AST功能,也就是用另一个Interpreter来运算AST,我们可以用Map[String,String]来模拟输入输出环境:

 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 }

Tester必须是个Monad,所以我们必须提供隐式对象testerMonad。看看运算结果:

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   }

运行foldRun的结果如下:

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)

下一个是runM了,它的入参数就是一个S[_]到M[_]的转换函数:f: S[Free[S,A]]=>M[Free[S,A]]。我们先实现了这个f函数:

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); n
9 }

测试运行runM:

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

我们曾经介绍过有些F[_]是无法实现map函数的,因此无法成为Functor,如以下ADT:

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

从Calc无法获取B类型值,所以无法实现Calc.map,因而Calc无法成为Functor。runFC就是专门为运算Calc这样的非Functor高阶类型值的。runFC需要一个FreeC[S,A]类型入参数:

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

可以得出runFC是专门为Coyoneda设计的。Coyoneda可以替代Calc[A],又是一个Functor,所以可以用Free产生Calc类型的Monad。我们先把Interpreter实现了:

 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 }

这个Interpreter用的是Stack内元素操作的运算方式。用runFC对ast运算的结果:

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

以上示范了针对任何抽象的Monadic Programm,我们如何通过各种Interpreter的具体实现方式来确定程序功能的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏微信公众号:Java团长

Java基础精选,你答对了几道?

但是当你成为一个资深的工程师的时候,很多公司并不希望你还是那样平庸,没有深度。虽然你会纳闷,我就算有深度你们也不一定用得上呀?然而到了这个级别的人需求量并不像初...

310
来自专栏函数式编程语言及工具

Scalaz(25)- Monad: Monad Transformer-叠加Monad效果

中间插播了几篇scalaz数据类型,现在又要回到Monad专题。因为FP的特征就是Monad式编程(Monadic programming),所以必须充分理解...

1826
来自专栏函数式编程语言及工具

Scalaz(33)- Free :算式-Monadic Programming

在任何模式的编程过程中都无法避免副作用的产生。我们可以用F[A]这种类型模拟FP的运算指令:A是可能产生副作用的运算,F[_]是个代数数据类型ADT(Alg...

1517
来自专栏Script Boy (CN-SIMO)

软件工程作业02

题目:      二柱子又对自己提出了新的要求: ? 设计思想: 项目名称、源文件等见软件工程作业01 对于乘除法,其实我们作业01中已经有了除法,别忘了...

1860
来自专栏Java与Android技术栈

使用Kotlin高效地开发Android App(一)

最近我们在做区块链相关的钱包项目,新的App使用全新的技术栈。在Android中我们使用Kotlin+RxJava+Android Architecture C...

512
来自专栏Java技术栈

跟我学 Java 8 新特性之 Stream 流(六)收集

我们前面的五篇文章基本都是在说将一个集合转成一个流,然后对流进行操作,其实这种操作是最多的,但有时候我们也是需要从流中收集起一些元素,并以集合的方式返回,我们把...

802
来自专栏余林丰

建造者模式

对于建造者模式,我们首先来说明建造者模式是用来干嘛的。建造模式一般用于创建复杂对象,这些复杂对象的构建过程是稳定的,但是内部的构件通常要面临比较复杂的变化。怎么...

1816
来自专栏IT笔记

Java基础精选,你答对了几道?

没有技术深度是大多程序员的一种常态。 但是当你成为一个资深的工程师的时候,很多公司并不希望你还是那样平庸,没有深度。虽然你会纳闷,我就算有深度你们也不一定用得上...

2555
来自专栏Android 开发者

[译] Kotlin 揭秘:理解并速记 Lambda 语法

在奥地利旅行期间,我参观了维也纳的奥地利国家图书馆。特别是国会大厅,这个令人惊叹的空间感觉就像印第安纳琼斯电影中的一些东西。房间周围的空间是这些门被装在架子上,...

710
来自专栏冰霜之地

iOS 如何实现Aspect Oriented Programming (上)

在“Runtime病院”住院的后两天,分析了一下AOP的实现原理。“出院”后,发现Aspect库还没有详细分析,于是就有了这篇文章,今天就来说说iOS 是如何实...

652

扫码关注云+社区