Scalaz（33）－ Free ：算式－Monadic Programming

  在任何模式的編程過程中都無法避免副作用的產生。我們可以用F[A]這種類型模擬FP的運算指令：A是可能產生副作用的運算，F[_]是個代數數據類型ADT(Algebraic Data Type)，可以實現函數組合（functional composition），我們可以不用理會A，先用F[_]來組合形成描述功能的抽象程式AST(Abstract Syntax Tree)，對A的運算可以分開另一個過程去實現，而且可以有多種的運算實現方式，這樣就達到了算式AST（Monadic Programming）、演算法（Interpretation）的所謂關註分離（separation of concern）目的。在前面的討論中我們介紹過：我們可以把任何F[A]升格成Monad，而Monad具備最完善的函數組合性能，特別是它支持for-comprehension這種表達方式。我們可以在for-comprehension框架里進行我們熟悉的行令編程（imperative programming），可以使程式意思表達更加顯而易見。

下麵我們來做一個簡單的示範：模擬一個互動智力算數測試（math quiz)：在系統提示下，用戶輸入第一個數字、再輸入第二個數字、再輸入操作符號、系統輸出算數操作結果。我們可以設計ADT如下：

1 sealed trait Quiz[+Next]
2 case class Question[Next](que: String, n: String => Next) extends Quiz[Next]
3 case class Answer[Next](ans: String, n: Next) extends Quiz[Next]

Quiz類型可能屬於Question或Answer。Question需要讀取一個String類型輸入，由於實際需要的可能是一個Int或者是Char，在獲取輸入後還要進行下一步類型轉換（map），所以還必須把一個轉換函數String=>Next存放入Question結構。Answer則不需要任何輸入，所以我們會把()作為Next的值存入Answer結構。

我們可以map over Next類型獲取Quiz的Functor實例：

1   implicit object QFunctor extends Functor[Quiz] {
2     def map[A,B](qa: Quiz[A])(f: A => B): Quiz[B] =
3       qa match {
4          case q: Question[A] => Question(q.que, q.n andThen f)
5          case Answer(a,n) => Answer(a,f(n))
6       }
7   }

從case q: Question[A]可以看出來：map over Next實際上是連續運算（andThen）。

我們再來幾個操作幫助方法：

 1 //操作幫助方法helper methods
 2   def askNumber(q: String) = Question(q, (inputString => inputString.toInt))  //_.toInt
 3   def askOperator(q: String) = Question(q, (inputString => inputString.head.toUpper.toChar))
 4   def answer(fnum: Int, snum: Int, opr: Char) = {
 5     def result =
 6       opr match {
 7         case 'A' => fnum + snum
 8         case 'M' => fnum * snum
 9         case 'D' => fnum / snum
10         case 'S' => fnum - snum
11       }
12     Answer("my answer is: " + result.toString,())
13   }

我們現在可以這樣編寫AST了： 

1 import Quiz._
2 val prg = for {
3  fn <- askNumber("The first number is:")
4  sn <- askNumber("The second number is:")
5  op <- askOperator("The operation is:")
6  _ <- answer(fn,sn,op)
7 } yield()                                         //> prg  : scalaz.Free[Exercises.interact.Quiz,Unit] = Gosub()

但是，askNumber,askOperator及answer這幾個操作函數都返回了Quiz類型，而Quiz類型不是Monad，不支持for-comprehension。我們可以用個隱式轉換把所有Quiz[A]升格成Free[Quiz,A]：

1   implicit def quizToFree[A](qz: Quiz[A]): Free[Quiz,A] = Free.liftF(qz)

這個示範完整的源代碼如下：

 1 sealed trait Quiz[+Next]
 2 object Quiz {
 3 //問題que:String, 等待String 然後轉成數字或操作符號
 4   case class Question[Next](que: String, n: String => Next) extends Quiz[Next]
 5   case class Answer[Next](ans: String, n: Next) extends Quiz[Next]
 6   implicit object QFunctor extends Functor[Quiz] {
 7     def map[A,B](qa: Quiz[A])(f: A => B): Quiz[B] =
 8       qa match {
 9          case q: Question[A] => Question(q.que, q.n andThen f)
10          case Answer(a,n) => Answer(a,f(n))
11       }
12   }
13 //操作幫助方法helper methods
14   def askNumber(q: String) = Question(q, (inputString => inputString.toInt))  //_.toInt
15   def askOperator(q: String) = Question(q, (inputString => inputString.head.toUpper.toChar)) //_.head.toUpper.toChar
16   def answer(fnum: Int, snum: Int, opr: Char) = {
17     def result =
18       opr match {
19         case 'A' => fnum + snum
20         case 'M' => fnum * snum
21         case 'D' => fnum / snum
22         case 'S' => fnum - snum
23       }
24     Answer("my answer is: " + result.toString,())
25   }
26   implicit def quizToFree[A](qz: Quiz[A]): Free[Quiz,A] = Free.liftF(qz)
27 }
28 import Quiz._
29 val prg = for {
30  fn <- askNumber("The first number is:")
31  sn <- askNumber("The second number is:")
32  op <- askOperator("The operation is:")
33  _ <- answer(fn,sn,op)
34 } yield()                                         //> prg  : scalaz.Free[Exercises.interact.Quiz,Unit] = Gosub()

再看看下麵的例子。試著猜測程式的作用：

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

從上面的AST表達方式可以估計到這是一個對Int進行加減乘除的計算器，應該是先通過push把操作對象存入一個Stack。然後對Stack內部的數字進行計算操作。具體是如何實現的，在這個階段無需知道，這應該是Interpreter的工作。這個例子不就真正體現了算式演算法的關註分離了的精髓嘛。