在上面几期讨论中我们连续介绍了Free Monad。因为FP是纯函数编程,也既是纯函数的组合集成,要求把纯代码和副作用代码可以分离开来。Free Monad的程序描述(AST)和程序实现(Interpretation)关注分离(separation of concern)模式恰恰能满足FP要求。我们可以用一些代数数据类型(ADT Algebraic Data Type)来模拟功能,再把这些ADT组合起来形成AST(Abstract Syntax Tree)。AST既是对程序功能的描述,它的组成过程也就是Monadic Programming了。在另外一个过程中,我们可以按需要去实现各种Interpreter,从而达到实际运算的目的。我认为既然FP也被称为Monadic Programming,那么Free Monad应该是FP里最重要的数据结构,它的应用模式代表了主流FP,应该有个规范的具体使用方式。在本次讨论中我们将会集中对Free Monad的应用模式进行示范体验。
我们在这次示范中模拟一个针对键值存储(Key Value Store)的操作例子:
1、ADT设计
1 sealed trait KVS[+Next] 2 object KVS { 3 case class Get[Next](key: String, onValue: String => Next) extends KVS[Next] 4 case class Put[Next](key: String, value: String, n: Next) extends KVS[Next] 5 case class Del[Next](key: String, n: Next) extends KVS[Next]
KVS[+Next]就是一种F[A]类型。从Suspend[F[Free[F,A]]可以得出A类型即Free类型,那么Next就是一个Free类,代表Free的下一个状态。如果需要使用Next,F[_]必须是个Functor, 这样才能通过F.map(A=>B)来获取F[B],B==另一个Free。 Put,Del模拟了无返回结果指令,那么如果需要链接到下一个Free状态的话就直接把一个Free放人Next位置。Get返回一个String,onValue函数接过这个返回值再连接到下一个Free状态。
2、获取Functor实例
1 implicit val kvsFunctor = new Functor[KVS] { 2 def map[A,B](kvs: KVS[A])(f: A => B): KVS[B] = kvs match { 3 case Get(key, onResult) => Get(key, onResult andThen f) 4 case Put(key, value, next) => Put(key,value,f(next)) 5 case Del(key,next) => Del(key,f(next)) 6 } 7 }
把A转换成B就是把Free[KVS,A]转成Free[KVS,B],其实就是map over Next,对Next进行转换。对于函数C=>Next,map就是函数组合了:(C=>Next) andThen (Next=>B)。
3、类型升格,lift to Free
1 implicit def kvsToFree[A](ka: KVS[A]): Free[KVS,A] = Free.liftF(ka) 2 def put(key: String , value: String): Free[KVS,Unit] = Free.liftF(Put(key,value,())) 3 def get(key: String): Free[KVS,String] = Free.liftF(Get(key,identity)) 4 def del(key: String): Free[KVS,Unit] = Free.liftF(Del(key,()))
包括隐式类型转换kvsToFree,可以把任何KVS[A]升格成Free[KVS,A]。独立指令升格put,get,del,因为不涉及下一个状态所以使用了()和identity。
4、Composition,Free Monad组合
1 import KVS._ 2 def modify(key: String, f: String => String): Free[KVS,Unit] =
3 for { 4 v <- Get(key,identity) 5 _ <- Put(key,f(v), ()) 6 } yield() //> modify: (key: String, f: String => String)scalaz.Free[Exercises.freeExamples.KVS,Unit]
通过隐式函数kvsToFree把ADT Get,Put升格成Free[KVS,A],然后实现函数组合。
5、功能描述,AST设计
1 val script = for { 2 _ <- put("USA","United States Of America") 3 _ <- put("CHN","China") 4 _ <- put("PIL","Pilipines") 5 _ <- put("JPN","Japan") 6 _ <- modify("CHN",_ =>"People's Republic Of China") 7 _ <- del("PIL") 8 chn <- get("CHN") 9 } yield chn //> script : scalaz.Free[Exercises.freeExamples.KVS,String] = Gosub()
使用的是独立直接升格指令函数。函数直接返回了Free类型。就像是在for-loop里进行我们熟悉的行令编程:逐条指令编写。
6、功能实现,Interpretation
a、尾递归编译,tail-recursive interpretation
1 def foldScript(kvs: Free[KVS,String],table: Map[String,String] = Map.empty): Map[String,String] =
2 kvs.resume.fold ( 3 { 4 case Get(key,onResult) => foldScript(onResult(table(key)), table) 5 case Put(key,value, next) => foldScript(next, table + (key -> value)) 6 case Del(key,next) => foldScript(next, table - key) 7 }, 8 _ => table 9 ) //> foldScript: (kvs: scalaz.Free[Exercises.freeExamples.KVS,String], table: Map[String,String]