Scalaz(36)- Free :实践-Free In Action

来源:互联网 时间:2016-03-28

  在上面几期讨论中我们连续介绍了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 }

 

 

 

 

 

 

 

 

 

相关阅读:
Top