首页 > 代码库 > Cats（2）－ Free语法组合，Coproduct-ADT composition
Cats（2）－ Free语法组合，Coproduct-ADT composition
上篇我们介绍了Free类型可以作为一种嵌入式编程语言DSL在函数式编程中对某种特定功能需求进行描述。一个完整的应用可能会涉及多样的关联功能，但如果我们为每个应用都设计一套DSL的话，那么在我们的函数式编程中将会不断重复的功能相似的DSL。我们应该秉承函数式编程的核心思想：函数组合（compositionality）来实现DSL的组合：把DSL拆解成最基础语句ADT，然后用这些ADT来组合成适合应用功能要求的完整DSL。我们还是使用上篇那个Interact DSL，这次再增加一个Login功能：
1 package demo.app 2 import cats.free.{Free,Inject} 3 object FreeModules { 4 object ADTs { 5 sealed trait Interact[+A] 6 object Interact { 7 case class Ask(prompt: String) extends Interact[String] 8 case class Tell(msg: String) extends Interact[Unit] 9 type FreeInteract[A] = Free[Interact,A]10 def ask(prompt: String): FreeInteract[String] = Free.liftF(Ask(prompt))11 def tell(msg: String): FreeInteract[Unit] = Free.liftF(Tell(msg))12 }13 14 sealed trait Login[+A]15 object Login {16 type FreeLogin[A] = Free[Login,A]17 case class Authenticate(user: String, pswd: String) extends Login[Boolean]18 def authenticate(user: String, pswd: String): FreeLogin[Boolean] =19 Free.liftF(Authenticate(user,pswd))20 }21 22 }23 24 }上面我们增加了个Login类。我们先来进行DSL编程：
1 object DSLs { 2 import ADTs._ 3 import Interact._ 4 import Login._ 5 val interactDSL: FreeInteract[Unit] = for { 6 first <- ask("What‘s your first name?") 7 last <- ask("What‘s your last name?") 8 _ <- tell(s"Hello, $first $last!") 9 } yield()10 11 val loginDSL: FreeLogin[Boolean] = for {12 login <- authenticate("Tiger","123")13 } yield login14 }很明显，用一种DSL编程是无法满足Login功能需要的。我们需要像下面这样的DSL：
1 val interactLoginDSL: Free[???,Boolean] = for {2 uid <- ask("Enter your User ID:")3 psw <- ask("Enter your Password:")4 aut <- authenticate(uid,pwd)5 } yield aut不过上面的???应该是什么呢？它应该是Interact和Login的集合。cats提供了Coproduct，它是一个树形数据结构：
/** `F` on the left and `G` on the right of [[scala.util.Either]]. * * @param run The underlying [[scala.util.Either]]. */final case class Coproduct[F[_], G[_], A](run: Either[F[A], G[A]]) {...}Coproduct 的每一个节点（Either[F[A],G[A]]）都是一个ADT，F[A]或者G[A]。我们可以用多层递归Coproduce结构来构建一个多语法的树形结构，如：
1 type H[A] = Coproduct[F,G,A]2 type I[A] = Coproduct[H,X,A]3 type J[A] = Coproduct[J,Y,A] //ADT(F,G,X,Y)用Coproduct的树形结构可以容纳多种DSL的ADT。在上面的例子里我们需要一个组合的语法InteractLogin：
1 type InteractLogin[A] = Coproduct[Interact,Login,A]cats提供了Inject类来构建Coproduct：
sealed abstract class Inject[F[_], G[_]] { def inj[A](fa: F[A]): G[A] def prj[A](ga: G[A]): Option[F[A]]}private[free] sealed abstract class InjectInstances { implicit def catsFreeReflexiveInjectInstance[F[_]]: Inject[F, F] = new Inject[F, F] { def inj[A](fa: F[A]): F[A] = fa def prj[A](ga: F[A]): Option[F[A]] = Some(ga) } implicit def catsFreeLeftInjectInstance[F[_], G[_]]: Inject[F, Coproduct[F, G, ?]] = new Inject[F, Coproduct[F, G, ?]] { def inj[A](fa: F[A]): Coproduct[F, G, A] = Coproduct.leftc(fa) def prj[A](ga: Coproduct[F, G, A]): Option[F[A]] = ga.run.fold(Some(_), _ => None) } implicit def catsFreeRightInjectInstance[F[_], G[_], H[_]](implicit I: Inject[F, G]): Inject[F, Coproduct[H, G, ?]] = new Inject[F, Coproduct[H, G, ?]] { def inj[A](fa: F[A]): Coproduct[H, G, A] = Coproduct.rightc(I.inj(fa)) def prj[A](ga: Coproduct[H, G, A]): Option[F[A]] = ga.run.fold(_ => None, I.prj) }}inj[A](fa: F[A]):G[A]代表将F[A]注入更大的语法集G[A]。cats提供了三种实现了ink函数的Inject隐式实例：
1、catsFreeReflexiveInjectInstance:Inject[F,F]：对单一语法，无须构建Coproduct
2、catsFreeLeftInjectInstance:Inject[F,Coproduct[F,G,?]]：构建Coproduct结构并将F放在左边
3、catsFreeRightInjectInstance:Inject[F,Coproduct[H,G,?]]：把F注入到已经包含H,G的Coproduct[H,G,?]
有了这三种实例后我们可以根据解析到的隐式实例类型使用inj函数通过Coproduct构建更大的语法集了。我们可以通过implicitly来验证一下Interact和Login语法的Inject隐式实例：
1 val selfInj = implicitly[Inject[Interact,Interact]]2 type LeftInterLogin[A] = Coproduct[Interact,Login,A]3 val leftInj = implicitly[Inject[Interact,LeftInterLogin]]4 type RightInterLogin[A] = Coproduct[Login,LeftInterLogin,A]5 val rightInj = implicitly[Inject[Interact,RightInterLogin]]现在我们可以用Inject.inj和Free.liftF把Interact和Login升格成Free[G,A]。G是个类型变量，Interact和Login在Coproduct的最终左右位置由当前Inject隐式实例类型决定：
1 object ADTs { 2 sealed trait Interact[+A] 3 object Interact { 4 case class Ask(prompt: String) extends Interact[String] 5 case class Tell(msg: String) extends Interact[Unit] 6 type FreeInteract[A] = Free[Interact,A] 7 //def ask(prompt: String): FreeInteract[String] = Free.liftF(Ask(prompt)) 8 //def tell(msg: String): FreeInteract[Unit] = Free.liftF(Tell(msg)) 9 def ask[G[_]](prompt: String)(implicit I: Inject[Interact,G]): Free[G,String] =10 Free.liftF(I.inj(Ask(prompt)))11 def tell[G[_]](msg: String)(implicit I: Inject[Interact,G]): Free[G,Unit] =12 Free.liftF(I.inj(Tell(msg)))13 }14 15 sealed trait Login[+A]16 object Login {17 type FreeLogin[A] = Free[Login,A]18 case class Authenticate(user: String, pswd: String) extends Login[Boolean]19 //def authenticate(user: String, pswd: String): FreeLogin[Boolean] =20 // Free.liftF(Authenticate(user,pswd))21 def authenticate[G[_]](user: String, pswd: String)(implicit I: Inject[Login,G]): Free[G,Boolean] =22 Free.liftF(I.inj(Authenticate(user,pswd)))23 }现在我们可以用混合语法的DSL来编程了：
1 object DSLs { 2 import ADTs._ 3 import Interact._ 4 import Login._ 5 val interactDSL: FreeInteract[Unit] = for { 6 first <- ask("What‘s your first name?") 7 last <- ask("What‘s your last name?") 8 _ <- tell(s"Hello, $first $last!") 9 } yield()10 11 val loginDSL: FreeLogin[Boolean] = for {12 login <- authenticate("Tiger","123")13 } yield login14 15 type InteractLogin[A] = Coproduct[Interact,Login,A]16 val interactLoginDSL: Free[InteractLogin,Boolean] = for {17 uid <- ask[InteractLogin]("Enter your User ID:")18 pwd <- ask[InteractLogin]("Enter your Password:")19 aut <- authenticate[InteractLogin](uid,pwd)20 } yield aut21 }在interactLoginDSL里所有ADT通过Inject隐式实例都被自动升格成统一的Free[Coproduct[Interact,Login,A]]。
interactLogin的功能实现方式之一示范如下：
1 object IMPLs { 2 import cats.{Id,~>} 3 import ADTs._,Interact._,Login._ 4 import DSLs._ 5 object InteractConsole extends (Interact ~> Id) { 6 def apply[A](ia: Interact[A]): Id[A] = ia match { 7 case Ask(p) => {println(p); readLine} 8 case Tell(m) => println(m) 9 }10 }11 object LoginMock extends (Login ~> Id) {12 def apply[A](la: Login[A]): Id[A] = la match {13 case Authenticate(u,p) => if (u == "Tiger" && p == "123") true else false14 }15 }16 val interactLoginMock: (InteractLogin ~> Id) = InteractConsole.or(LoginMock)17 }这个interactLoginMock就是一个Interact,Login混合语法程序的功能实现。不过我们还是应该赋予Login一个比较实在点的实现：我们可以用一种依赖注入方式通过Reader数据类型把外部系统的用户密码验证的方法传入：
1 import Dependencies._ 2 import cats.data.Reader 3 type ReaderPass[A] = Reader[PasswordControl,A] 4 object LoginToReader extends (Login ~> ReaderPass) { 5 def apply[A](la: Login[A]): ReaderPass[A] = la match { 6 case Authenticate(u,p) => Reader{pc => pc.matchUserPassword(u,p)} 7 } 8 } 9 object InteractToReader extends (Interact ~> ReaderPass) {10 def apply[A](ia: Interact[A]): ReaderPass[A] = ia match {11 case Ask(p) => {println(p); Reader(pc => readLine)}12 case Tell(m) => {println(m); Reader(pc => ())}13 }14 }15 val userLogin: (InteractLogin ~> ReaderPass) = InteractToReader or LoginToReader假设用户密码验证由外部另一个系统负责，PasswordControl是与这个外部系统的界面（interface）：
1 object Dependencies {2 trait PasswordControl {3 val mapPasswords: Map[String,String]4 def matchUserPassword(uid: String, pwd: String): Boolean5 }6 }我们用Reader来注入PasswordControl这个外部依赖（dependency injection IOC）。因为Interact和Login结合形成的是一个统一的语句集，所以我们必须进行Interact与?ReaderPass对应。下面我们先构建一个PasswordControl对象作为模拟数据，然后试运行：
1 object catsComposeFree extends App { 2 import Dependencies._ 3 import FreeModules._ 4 import DSLs._ 5 import IMPLs._ 6 object UserPasswords extends PasswordControl { 7 override val mapPasswords: Map[String, String] = Map( 8 "Tiger" -> "123", 9 "John" -> "456"10 )11 override def matchUserPassword(uid: String, pwd: String): Boolean =12 mapPasswords.getOrElse(uid,pwd+"!") == pwd13 }14 15 val r = interactLoginDSL.foldMap(userLogin).run(UserPasswords)16 println(r)17 18 }运算结果：
1 Enter your User ID: 2 Tiger 3 Enter your Password: 4 123 5 true 6 ... 7 Enter your User ID: 8 Chan 9 Enter your Password:10 12311 false我们再用这个混合的DSL编个稍微完整点的程序：
1 val userLoginDSL: Free[InteractLogin,Unit] = for {2 uid <- ask[InteractLogin]("Enter your User ID:")3 pwd <- ask[InteractLogin]("Enter your Password:")4 aut <- authenticate[InteractLogin](uid,pwd)5 _ <- if (aut) tell[InteractLogin](s"Hello $uid")6 else tell[InteractLogin]("Sorry, who are you?")7 } yield()运算这个程序不需要任何修改：
1 //val r = interactLoginDSL.foldMap(userLogin).run(UserPasswords)2 //println(r)3 userLoginDSL.foldMap(userLogin).run(UserPasswords)现在结果变成了：
1 Enter your User ID: 2 Tiger 3 Enter your Password: 4 123 5 Hello Tiger 6 ... 7 Enter your User ID: 8 CHAN 9 Enter your Password:10 12311 Sorry, who are you?如果我们在这两个语法的基础上再增加一个模拟权限管理的语法，ADT设计如下：
1 sealed trait Auth[+A]2 object Auth {3 case class Authorize(uid: String) extends Auth[Boolean]4 def authorize[G[_]](uid:String)(implicit I: Inject[Auth,G]): Free[G,Boolean] =5 Free.liftF(I.inj(Authorize(uid)))6 }假设实际的权限管理依赖外部系统，我们先定义它的界面：
1 object Dependencies { 2 trait PasswordControl { 3 val mapPasswords: Map[String,String] 4 def matchUserPassword(uid: String, pwd: String): Boolean 5 } 6 trait PermControl { 7 val mapAuthorized: Map[String,Boolean] 8 def authorized(uid: String): Boolean 9 }10 }再用三种语法合成的DSL来编一段程序：
1 import Auth._ 2 type Permit[A] = Coproduct[Auth,InteractLogin,A] 3 val userPermitDSL: Free[Permit,Unit] = for { 4 uid <- ask[Permit]("Enter your User ID:") 5 pwd <- ask[Permit]("Enter your Password:") 6 auth <- authenticate[Permit](uid,pwd) 7 perm <- if(auth) authorize[Permit](uid) 8 else Free.pure[Permit,Boolean](false) 9 _ <- if (perm) tell[Permit](s"Hello $uid, welcome to the program!")10 else tell[Permit]("Sorry, no no no!")11 } yield()很遗憾，这段代码无法通过编译，cats还无法处理多层递归Coproduct。对Coproduct的处理scalaz还是比较成熟的，我在之前写过一篇scalaz Coproduct Free的博客，里面用的例子就是三种语法的DSL。实际上不单只是Coproduct的问题，现在看来cats.Free对即使很简单的应用功能也有着很复杂无聊的代码需求，这是我们无法接受的。由于Free编程在函数式编程里占据着如此重要的位置，我们暂时还没有其它选择，所以必须寻找一个更好的编程工具才行，freeK就是个这样的函数组件库。我们将在下篇讨论里用freeK来实现多种语法DSL编程。
无论如何，我还是把这篇讨论的示范代码附在下面：
1 import cats.data.Coproduct 2 import cats.free.{Free, Inject} 3 object FreeModules { 4 object ADTs { 5 sealed trait Interact[+A] 6 object Interact { 7 case class Ask(prompt: String) extends Interact[String] 8 case class Tell(msg: String) extends Interact[Unit] 9 type FreeInteract[A] = Free[Interact,A] 10 //def ask(prompt: String): FreeInteract[String] = Free.liftF(Ask(prompt)) 11 //def tell(msg: String): FreeInteract[Unit] = Free.liftF(Tell(msg)) 12 def ask[G[_]](prompt: String)(implicit I: Inject[Interact,G]): Free[G,String] = 13 Free.liftF(I.inj(Ask(prompt))) 14 def tell[G[_]](msg: String)(implicit I: Inject[Interact,G]): Free[G,Unit] = 15 Free.liftF(I.inj(Tell(msg))) 16 } 17 18 sealed trait Login[+A] 19 object Login { 20 type FreeLogin[A] = Free[Login,A] 21 case class Authenticate(user: String, pswd: String) extends Login[Boolean] 22 //def authenticate(user: String, pswd: String): FreeLogin[Boolean] = 23 // Free.liftF(Authenticate(user,pswd)) 24 def authenticate[G[_]](user: String, pswd: String)(implicit I: Inject[Login,G]): Free[G,Boolean] = 25 Free.liftF(I.inj(Authenticate(user,pswd))) 26 } 27 28 sealed trait Auth[+A] 29 object Auth { 30 case class Authorize(uid: String) extends Auth[Boolean] 31 def authorize[G[_]](uid:String)(implicit I: Inject[Auth,G]): Free[G,Boolean] = 32 Free.liftF(I.inj(Authorize(uid))) 33 } 34 val selfInj = implicitly[Inject[Interact,Interact]] 35 type LeftInterLogin[A] = Coproduct[Interact,Login,A] 36 val leftInj = implicitly[Inject[Interact,LeftInterLogin]] 37 type RightInterLogin[A] = Coproduct[Login,LeftInterLogin,A] 38 val rightInj = implicitly[Inject[Interact,RightInterLogin]] 39 } 40 41 object DSLs { 42 import ADTs._ 43 import Interact._ 44 import Login._ 45 val interactDSL: FreeInteract[Unit] = for { 46 first <- ask("What‘s your first name?") 47 last <- ask("What‘s your last name?") 48 _ <- tell(s"Hello, $first $last!") 49 } yield() 50 51 val loginDSL: FreeLogin[Boolean] = for { 52 login <- authenticate("Tiger","123") 53 } yield login 54 55 type InteractLogin[A] = Coproduct[Interact,Login,A] 56 val interactLoginDSL: Free[InteractLogin,Boolean] = for { 57 uid <- ask[InteractLogin]("Enter your User ID:") 58 pwd <- ask[InteractLogin]("Enter your Password:") 59 aut <- authenticate[InteractLogin](uid,pwd) 60 } yield aut 61 val userLoginDSL: Free[InteractLogin,Unit] = for { 62 uid <- ask[InteractLogin]("Enter your User ID:") 63 pwd <- ask[InteractLogin]("Enter your Password:") 64 aut <- authenticate[InteractLogin](uid,pwd) 65 _ <- if (aut) tell[InteractLogin](s"Hello $uid") 66 else tell[InteractLogin]("Sorry, who are you?") 67 } yield() 68 /* import Auth._ 69 type Permit[A] = Coproduct[Auth,InteractLogin,A] 70 val userPermitDSL: Free[Permit,Unit] = for { 71 uid <- ask[Permit]("Enter your User ID:") 72 pwd <- ask[Permit]("Enter your Password:") 73 auth <- authenticate[Permit](uid,pwd) 74 perm <- if(auth) authorize[Permit](uid) 75 else Free.pure[Permit,Boolean](false) 76 _ <- if (perm) tell[Permit](s"Hello $uid, welcome to the program!") 77 else tell[Permit]("Sorry, no no no!") 78 } yield() */ 79 } 80 object IMPLs { 81 import cats.{Id,~>} 82 import ADTs._,Interact._,Login._ 83 import DSLs._ 84 object InteractConsole extends (Interact ~> Id) { 85 def apply[A](ia: Interact[A]): Id[A] = ia match { 86 case Ask(p) => {println(p); readLine} 87 case Tell(m) => println(m) 88 } 89 } 90 object LoginMock extends (Login ~> Id) { 91 def apply[A](la: Login[A]): Id[A] = la match { 92 case Authenticate(u,p) => if (u == "Tiger" && p == "123") true else false 93 } 94 } 95 val interactLoginMock: (InteractLogin ~> Id) = InteractConsole.or(LoginMock) 96 import Dependencies._ 97 import cats.data.Reader 98 type ReaderPass[A] = Reader[PasswordControl,A] 99 object LoginToReader extends (Login ~> ReaderPass) {100 def apply[A](la: Login[A]): ReaderPass[A] = la match {101 case Authenticate(u,p) => Reader{pc => pc.matchUserPassword(u,p)}102 }103 }104 object InteractToReader extends (Interact ~> ReaderPass) {105 def apply[A](ia: Interact[A]): ReaderPass[A] = ia match {106 case Ask(p) => {println(p); Reader(pc => readLine)}107 case Tell(m) => {println(m); Reader(pc => ())}108 }109 }110 val userLogin: (InteractLogin ~> ReaderPass) = InteractToReader or LoginToReader111 112 }113 }114 object Dependencies {115 trait PasswordControl {116 val mapPasswords: Map[String,String]117 def matchUserPassword(uid: String, pwd: String): Boolean118 }119 trait PermControl {120 val mapAuthorized: Map[String,Boolean]121 def authorized(uid: String): Boolean122 }123 }124 125 object catsComposeFree extends App {126 import Dependencies._127 import FreeModules._128 import DSLs._129 import IMPLs._130 object UserPasswords extends PasswordControl {131 override val mapPasswords: Map[String, String] = Map(132 "Tiger" -> "123",133 "John" -> "456"134 )135 override def matchUserPassword(uid: String, pwd: String): Boolean =136 mapPasswords.getOrElse(uid,pwd+"!") == pwd137 }138 139 //val r = interactLoginDSL.foldMap(userLogin).run(UserPasswords)140 //println(r)141 userLoginDSL.foldMap(userLogin).run(UserPasswords)142 143 }
Cats（2）－ Free语法组合，Coproduct-ADT composition
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。