Scalaz（36）－ Free ：实践－Free In Action – 实用体验详解编程语言

在上面几期讨论中我们连续介绍了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])Map[String,String] 
10  foldScript(script,Map.empty)     //> res0: Map[String,String] = Map(USA -> United States Of America, CHN -> People's Republic Of China, JPN -> Japan)

注意，fold其实是Either.fold。foldScript是个尾递归函数。这时候Next就成为下一步递归的链接了。

b、foldMap，高阶类型转换，Natural Transformation，F[A]～>G[A]

1 type KVState[A] = State[Map[String,String],A] 
2  object KvsToMap extends (KVS ~> KVState) { 
3    def apply[A](kvs: KVS[A]): KVState[A] = kvs match { 
4       case Get(key,onResult) => State { m => (m, onResult(m(key))) } 
5       case Put(key,value,next) => State { m => (m + (key -> value), next) } 
6       case Del(key,next) => State { m => (m - key, next) } 
7    } 
8  } 
9  script.foldMap(KvsToMap).run(Map.empty)          //> res1: scalaz.Id.Id[(Map[String,String], String)] = (Map(USA -> United States Of America, CHN -> People's Republic Of China, JPN -> Japan),People's Republic Of China)

c、mutable实现方法：

 1 def goScript(kvs: Free[KVS,String],table: scala.collection.mutable.Map[String,String]):Unit = 
 2    kvs.go { 
 3      case Get(key,onResult) => onResult(table(key)) 
 4      case Put(key,value,next) => table += (key -> value); next 
 5      case Del(key,next) => table -= key; next 
 6    }                  //> goScript: (kvs: scalaz.Free[Exercises.freeExamples.KVS,String], table: scala.collection.mutable.Map[String,String])Unit 
 7  val mutableMap = scala.collection.mutable.Map[String,String]() 
 8                       //> mutableMap  : scala.collection.mutable.Map[String,String] = Map() 
 9  goScript(script,mutableMap) 
10  println(mutableMap)  //> Map(JPN -> Japan, CHN -> People's Republic Of China, USA -> United States Of America)

把完整的示范源代码提供给大家：

 1 package Exercises 
 2 import scalaz._ 
 3 import Scalaz._ 
 4 import scala.language.higherKinds 
 5 import scala.language.implicitConversions 
 6 object freeExamples { 
 7 sealed trait KVS[+Next] 
 8 object KVS { 
 9  case class Get[Next](key: String, onValue: String => Next) extends KVS[Next] 
10  case class Put[Next](key: String, value: String, n: Next) extends KVS[Next] 
11  case class Del[Next](key: String, n: Next) extends KVS[Next] 
12   implicit val kvsFunctor = new Functor[KVS] { 
13      def map[A,B](kvs: KVS[A])(f: A => B): KVS[B] = kvs match { 
14        case Get(key, onResult) => Get(key, onResult andThen f) 
15        case Put(key, value, next) => Put(key,value,f(next)) 
16        case Del(key,next) => Del(key,f(next)) 
17      } 
18   } 
19  implicit def kvsToFree[A](ka: KVS[A]): Free[KVS,A] = Free.liftF(ka) 
20  def put(key: String , value: String): Free[KVS,Unit] = Free.liftF(Put(key,value,())) 
21  def get(key: String): Free[KVS,String] = Free.liftF(Get(key,identity)) 
22  def del(key: String): Free[KVS,Unit] = Free.liftF(Del(key,())) 
23 } 
24 import KVS._ 
25 def modify(key: String, f: String => String): Free[KVS,Unit] = 
26   for { 
27    v <- Get(key,identity) 
28    _ <- Put(key,f(v), ()) 
29   } yield() 
30 val script = for { 
31   _ <- put("USA","United States Of America") 
32   _ <- put("CHN","China") 
33   _ <- put("PIL","Pilipines") 
34   _ <- put("JPN","Japan") 
35   _ <- modify("CHN",_ =>"People's Republic Of China") 
36   _ <- del("PIL") 
37   chn <- get("CHN") 
38 } yield chn 
39  
40 def foldScript(kvs: Free[KVS,String],table: Map[String,String] = Map.empty): Map[String,String] = 
41   kvs.resume.fold ( 
42   { 
43     case Get(key,onResult) => foldScript(onResult(table(key)), table) 
44     case Put(key,value, next) => foldScript(next, table + (key -> value)) 
45     case Del(key,next) => foldScript(next, table - key) 
46   }, 
47   _ => table 
48  ) 
49  foldScript(script,Map.empty) 
50  
51  type KVState[A] = State[Map[String,String],A] 
52  object KvsToMap extends (KVS ~> KVState) { 
53    def apply[A](kvs: KVS[A]): KVState[A] = kvs match { 
54       case Get(key,onResult) => State { m => (m, onResult(m(key))) } 
55       case Put(key,value,next) => State { m => (m + (key -> value), next) } 
56       case Del(key,next) => State { m => (m - key, next) } 
57    } 
58  } 
59  script.foldMap(KvsToMap).run(Map.empty) 
60   
61  def goScript(kvs: Free[KVS,String],table: scala.collection.mutable.Map[String,String]):Unit = 
62    kvs.go { 
63      case Get(key,onResult) => onResult(table(key)) 
64      case Put(key,value,next) => table += (key -> value); next 
65      case Del(key,next) => table -= key; next 
66    } 
67  val mutableMap = scala.collection.mutable.Map[String,String]() 
68  goScript(script,mutableMap) 
69  println(mutableMap) 
70 }

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/industrynews/12912.html

Scalaz（36）－ Free ：实践－Free In Action – 实用体验详解编程语言

相关推荐

发表回复