后端【免费下载链接】catsLightweight, modular, and extensible library for functional programming.项目地址https://gitcode.com/gh_mirrors/ca/cats点击查看免费下载本文是 Cats 函数式编程库中cats-free模块的完整技术指南。自由单子Free Monad是一种从任意Functor构造出Monad的通用构造它允许你把程序当作纯数据来表示、组合与重解释先构建语法树再通过自然变换把它编译到任意目标解释器执行。读完本文你将掌握 Free Monad 的五大核心能力——把有状态计算表示为数据、栈安全地运行递归计算、构建嵌入式 DSL、用自然变换重定向计算到不同解释器以及用FreeT在构建 AST 的同时混入其他单子效应并能在真实项目中落地这些模式。本文全部内容基于 Cats 仓库中的官方 Free Monad 文档并辅以 Free.scala、FreeT.scala、InjectK.scala、EitherK.scala 等源码实现与测试用例作为佐证。什么是 Free Monad一个自由单子free monad是一种构造它允许你从任意Functor构建出一个Monad。和其他单子一样它是一种表示与操作计算的纯函数式方式。具体来说自由单子提供了以下实用能力将有状态的计算表示为数据并在之后运行它栈安全地运行递归计算构建嵌入式 DSL领域特定语言Domain-Specific Language使用自然变换natural transformation将计算重定向到另一个解释器。在 Cats 中表示自由单子的类型简写为Free[_]。从源码结构看Free的定义位于 free/src/main/scala/cats/free/Free.scala其核心注释明确写道A free operational monad for some functorS即针对某个函子S的自由操作单子并且绑定操作使用堆而非栈来完成从而实现尾调用消除。在 Cats 中表示自由单子的类型简写为Free[_]。使用 Free Monad添加依赖如果你想使用 Cats 的自由单子需要为项目添加cats-free模块的库依赖。在 Cats 仓库中cats-free模块在 build.sbt 中定义为跨平台项目JSPlatform / JVMPlatform / NativePlatformlazy val free crossProject(JSPlatform, JVMPlatform, NativePlatform) .crossType(CrossType.Pure) .dependsOn(core, tests % test-internal - test) .settings(moduleName : cats-free, name : Cats Free)在你的项目中通常只需要引入以 sbt 为例libraryDependencies org.typelevel %% cats-free % versioncats-free依赖cats-core包含Free、FreeT、Trampoline、Coyoneda等核心类型位于 free/src/main/scala/cats/free/。理解自由单子最好的方式是在实际代码中观察它——下面我们就用它来创建一个嵌入式 DSL。如果你对自由单子背后的范畴论理论感兴趣可以直接跳到文末的 理论章节。实战用 Free[_] 构建键值存储 DSL研究你的主题假设我们要为一个键值存储key-value store创建 DSL希望对键做三件事put将一个value关联到它的key存入存储get根据key从存储中取出valuedelete根据key从存储中删除value。我们的构想是用嵌入式 DSL 把这一系列操作写成一段程序编译这段程序最后执行它来真正地与键值存储交互。例如put(toto, 3) get(toto) // returns 3 delete(toto)同时我们希望计算被表示为纯的、不可变的值创建程序与执行程序分离能够支持多种不同的执行方式。研究你的语法与键值存储交互共有 3 条命令Put把一个值与一个键关联后存入存储Get根据键把关联的值从存储中取出Delete根据键把值从存储中删除。创建表示语法的 ADTADT 是Algebraic Data Type代数数据类型的缩写。在此语境下它指一组封闭的类型集合可以组合出复杂、递归的值。我们需要创建一个 ADT 来表示键值操作sealed trait KVStoreA[A] case class PutT extends KVStoreA[Unit] case class GetT extends KVStoreA[Option[T]] case class Delete(key: String) extends KVStoreA[Unit]注意这里每个 case class 都带有一个类型参数AKVStoreA[A]它表示这条操作执行成功后的返回类型Put和Delete返回UnitGet返回Option[T]。这个类型参数正是 Free Monad 能够把命令序列缝合成单子流程的关键——每个命令的返回类型会成为下一条命令的输入。释放Free你的 ADT把 ADT解放成 Free Monad 需要五个基本步骤创建基于Free[_]与KVStoreA[_]的类型使用liftF为KVStore[_]创建智能构造器smart constructors用键值 DSL 操作构建一个程序为 DSL 操作的程序构建一个编译器执行编译后的程序。1. 创建基于 ADT 的 Free 类型import cats.free.Free type KVStore[A] Free[KVStoreA, A]这里KVStore[A]就是Free[KVStoreA, A]的别名外层函子为KVStoreA最终计算结果类型为A。2. 使用 liftF 创建智能构造器这些方法会让 DSL 的使用体验好得多并把KVStoreA[_]的值提升到KVStore[_]单子中注意第二个类型参数少了字母 A。import cats.free.Free.liftF // Put returns nothing (i.e. Unit). def putT: KVStore[Unit] liftFKVStoreA, Unit) // Get returns a T value. def getT: KVStore[Option[T]] liftF[KVStoreA, Option[T]](GetT) // Delete returns nothing (i.e. Unit). def delete(key: String): KVStore[Unit] liftF(Delete(key)) // Update composes get and set, and returns nothing. def updateT: KVStore[Unit] for { vMaybe - getT _ - vMaybe.map(v putT)).getOrElse(Free.pure(())) } yield ()从源码看Free.liftF的实现极其简单def liftF[F[_], A](value: F[A]): Free[F, A] Suspend(value)它只是把F[A]包进Suspend节点。update展示了 Free Monad 的灵活之处get返回KVStore[Option[T]]借助Option的map/getOrElse可以优雅地处理键不存在的分支并用Free.pure(())作为空操作。3. 构建程序Program现在我们已经能构造KVStore[_]值可以用for-comprehension写出程序def program: KVStore[Option[Int]] for { _ - put(wild-cats, 2) _ - updateInt) _ - put(tame-cats, 5) n - getInt _ - delete(tame-cats) } yield n这看起来像是单子式流程但注意它实际上只是构建了一个递归数据结构用来表示操作序列。程序在构建阶段不产生任何执行效果。4. 为程序编写编译器Compiler现在你应该理解了Free[_]用来创建嵌入式 DSL。单独看这个 DSL 只表示一个操作序列由递归数据结构定义它本身不产生任何东西。Free[_]是你编程语言内部的编程语言所以和任何编程语言一样我们需要把抽象语言编译成有效的语言然后运行它。为此我们使用类型容器之间的自然变换。自然变换作用于F[_]和G[_]这样的类型之间这个特定的变换写作FunctionK[F, G]或使用符号别名F ~ G。在我们的例子中用一个简单的可变Map来表示键值存储import cats.arrow.FunctionK import cats.{Id, ~} import scala.collection.mutable // the program will crash if a type is incorrectly specified. def impureCompiler: KVStoreA ~ Id new (KVStoreA ~ Id) { // a very simple (and imprecise) key-value store val kvs mutable.Map.empty[String, Any] def applyA: Id[A] fa match { case Put(key, value) println(sput($key, $value)) kvs(key) value () case Get(key) println(sget($key)) kvs.get(key).asInstanceOf[A] case Delete(key) println(sdelete($key)) kvs.remove(key) () } }请注意这个impureCompiler是不纯的——它修改了kvs并且用println产生了日志输出。函数式编程的全部目的不是禁止副作用而是把副作用推到系统的边界以已知且可控的方式处理它们。Id[_]表示最简单的类型容器类型本身。因此Id[Int]就是Int。这意味着我们的程序会立即执行并阻塞直到最终值返回。然而我们很容易使用其他类型容器来获得不同的行为例如Future[_]异步计算List[_]收集多个结果Option[_]支持可选结果Either[E, *]支持失败一个伪随机单子支持不确定性等等……这种换一个解释器的能力正是 Free Monad 的核心价值同样的程序数据可以在不同语义下运行而程序本身无需任何修改。5. 运行你的程序最后一步自然是编译之后运行程序。Free[_]只是一个递归结构可以看作产生其他操作的操作序列。在这方面它与List[_]类似我们常用折叠如foldRight从列表中获得单个值——折叠遍历这个结构并合并其内容。运行Free[_]的思路完全相同折叠递归结构具体方式为消费每个操作用impureCompiler把操作编译到有效语言中如有副作用则应用它计算下一个操作递归继续直到到达Pure状态返回它。这个操作称为Free.foldMapfinal def foldMap[M[_]](f: FunctionK[S,M])(M: Monad[M]): M[A] ...M必须是一个Monad才能被展平著名的Monad之下的幺半群特质。由于Id是Monad我们可以使用foldMap。用之前的impureCompiler运行你的Freeval result: Option[Int] program.foldMap(impureCompiler)foldMap的一个重要特性是它的栈安全性stack-safety。它在栈上评估计算的每一步然后退栈并重新开始。这个过程称为trampolining蹦床。只要你的自然变换是栈安全的foldMap就永远不会栈溢出。蹦床是堆密集型的但栈安全性提供了使用Free[_]处理数据密集型任务以及流等无限进程所需的可靠性。从源码看Free.foldMap正是通过M.tailRecM实现栈安全的final def foldMap[M[_]](f: FunctionK[S, M])(implicit M: Monad[M]): M[A] M.tailRecM(this)(_.step match { case Pure(a) M.pure(Right(a)) case Suspend(sa) M.map(f(sa))(Right(_)) case FlatMapped(c, g) M.map(c.foldMap(f))(cc Left(g(cc))) })每次循环要么返回Right结果就绪要么返回Left继续计算把下一步做什么以堆上的值传递从而避免 JVM 调用栈的深度增长。6. 使用纯编译器可选前面的例子使用了带副作用的自然变换。这可行但你可能更愿意以更纯的方式折叠你的Free。State 数据结构可以在不可变Map中跟踪程序状态完全避免可变性import cats.data.State type KVStoreState[A] State[Map[String, Any], A] val pureCompiler: KVStoreA ~ KVStoreState new (KVStoreA ~ KVStoreState) { def applyA: KVStoreState[A] fa match { case Put(key, value) State.modify(_.updated(key, value)) case Get(key) State.inspect(_.get(key).asInstanceOf[A]) case Delete(key) State.modify(_ - key) } }可以看到我们又一次遇到了 Scala 的模式匹配受 JVM 类型擦除限制的地方但克服起来并不难。运行val result: (Map[String, Any], Option[Int]) program.foldMap(pureCompiler).run(Map.empty).value这里foldMap把KVStoreA的每条操作映射为一次State变换最终通过.run(Map.empty).value得到最终状态Map[String, Any]与结果Option[Int]的二元组——全程没有任何可变状态。相比impureCompiler纯编译器把程序的状态推进完全纳入类型系统天然可重放、可测试。栈安全的源码级验证自由单子栈安全的说法并非空谈FreeSuite.scala 中有大量直接测试toString 是栈安全的对Free.pureList, Int连续做100 万次map仍能正常输出tailRecM是栈安全的通过tailRecM递归 5 万次foldMap是栈安全的一个递归 1 万层的程序用Id解释器执行后正确返回10000.runTailRec与.run各 10 万次递归的flatMap链都能正常求值。这些测试共同印证了Free把递归编码在堆上而非栈上的设计结论。组合 Free Monads 的 ADT真实世界的应用常常需要组合不同的代数algebra。Swierstra 在Data types à la carte中描述的injection 类型类让我们可以在Free的上下文中组合不同的代数——在 Cats 中它就是InjectK位于 core/src/main/scala/cats/InjectK.scala在 Cats 1.0 之前称为Inject。让我们看一个简单例子把两个互不相关的 ADT 组合成一个EitherK从而形成更复杂的程序。import cats.data.EitherK import cats.free.Free import cats.{Id, InjectK, ~} import scala.collection.mutable.ListBuffer定义两个 ADT/* Handles user interaction */ sealed trait Interact[A] case class Ask(prompt: String) extends Interact[String] case class Tell(msg: String) extends Interact[Unit] /* Represents persistence operations */ sealed trait DataOp[A] case class AddCat(a: String) extends DataOp[Unit] case class GetAllCats() extends DataOp[List[String]]ADT 定义好后我们可以正式声明一个Free程序就是其各代数algebra的EitherK。type CatsApp[A] EitherK[DataOp, Interact, A]从源码看EitherK的底层就是scala.util.Either的类型构造器版本final case class EitherK[F[_], G[_], A](run: Either[F[A], G[A]])而InjectK提供一对互逆的注入/投影函数abstract class InjectK[F[_], G[_]] { def inj: FunctionK[F, G] // 从 F 无损注入到 G def prj: FunctionK[G, λ[α Option[F[α]]]] // 部分逆从 G 投影回 F }注入是不丢失任何信息的函子变换对于每个ga: G[A]至多有一个fa: F[A]满足inj(fa) ga。为了利用单子组合我们使用智能构造器把每个代数提升到Free上下文class Interacts[F[_]](implicit I: InjectK[Interact, F]) { def tell(msg: String): Free[F, Unit] Free.liftInjectF) def ask(prompt: String): Free[F, String] Free.liftInjectF) } object Interacts { implicit def interacts[F[_]](implicit I: InjectK[Interact, F]): Interacts[F] new Interacts[F] } class DataSource[F[_]](implicit I: InjectK[DataOp, F]) { def addCat(a: String): Free[F, Unit] Free.liftInjectF) def getAllCats: Free[F, List[String]] Free.liftInjectF) } object DataSource { implicit def dataSource[F[_]](implicit I: InjectK[DataOp, F]): DataSource[F] new DataSource[F] }这里的Free.liftInject[F]对应于源码中Free.liftInject在给定InjectK[F, G]的前提下把F[A]注入到G[A]后再liftF进 Freedef liftInject[G[_]]: FreeLiftInjectKPartiallyApplied[G] ... // 内部实现 // Free.liftF(I.inj(fa)) // I: InjectK[F, G]现在 ADT 可以轻松组合并在单子上下文中自然地交错使用def program(implicit I : Interacts[CatsApp], D : DataSource[CatsApp]): Free[CatsApp, Unit] { import I._, D._ for { cat - ask(Whats the kittys name?) _ - addCat(cat) cats - getAllCats _ - tell(cats.toString) } yield () }最后为每个 ADT 写一个解释器并用FunctionK组合成EitherK的解释器以便编译并应用到我们的Free程序object ConsoleCatsInterpreter extends (Interact ~ Id) { def applyA i match { case Ask(prompt) println(prompt) readLine() case Tell(msg) println(msg) } } object InMemoryDatasourceInterpreter extends (DataOp ~ Id) { private[this] val memDataSet new ListBuffer[String] def applyA fa match { case AddCat(a) memDataSet.append(a); () case GetAllCats() memDataSet.toList } } val interpreter: CatsApp ~ Id InMemoryDatasourceInterpreter or ConsoleCatsInterpreterInMemoryDatasourceInterpreter or ConsoleCatsInterpreter正是利用FunctionK的组合能力把两个分别针对DataOp与Interact的解释器合并成一个针对EitherK[DataOp, Interact, *]的解释器or即FunctionK.or对EitherK的左右两侧分别派发。现在运行我们的程序——提示输入时键入 snugglesimport DataSource._, Interacts._ val evaled: Unit program.foldMap(interpreter)执行时ask打印提示并从控制台读取名字addCat存入内存列表getAllCats取回列表tell打印结果——控制台上会看到类似List(snuggles)的输出。组合的关键意义在于Free程序本身完全不知道解释器的存在。你可以为同一组 ADT 编写任意多个解释器内存版、数据库版、测试桩版程序数据一字不改。For the curious ones: Free 在理论上是什么从数学角度讲一个自由单子至少在编程语言语境下是某个遗忘函子forgetful functor的左伴随构造该遗忘函子的定义域是 Monads 范畴陪域是 Endofunctors 范畴。是不是有点懵具体来说它只是一个巧妙的构造允许我们从任意函子构建一个非常简单的 Monad。上述遗忘函子取出一个Monad之后会遗忘其 monadic 部分例如flatMap函数遗忘其 pointed 部分例如pure函数保留其 functor 部分例如map函数。通过反转所有箭头来构造左伴随我们推断出自由单子基本上是这样一种构造它接受一个函子加上 pointed 部分例如pure加上 monadic 行为例如flatMap。在实现层面为了从函子构建单子我们使用下面这个经典的归纳定义sealed abstract class Free[F[_], A] case class Pure[F[_], A](a: A) extends Free[F, A] case class Suspend[F[_], A](a: F[Free[F, A]]) extends Free[F, A]这推广了不动点函子的概念。在这个表示中Pure从一个A值构建Free实例它物化了pure函数Suspend通过把F应用于先前的Free来构建新的Free它物化了flatMap函数。于是一个典型的Free结构可能长这样Suspend(F(Suspend(F(Suspend(F(....(Pure(a))))))))Free是一个递归结构。它把F[A]中的A当作递归的载体carrier以Pure作为终止元素。从计算的角度看Free递归结构可以看作操作序列Pure返回一个A值并结束整个计算Suspend是一个续体continuation它用挂起函子F例如可以表示一条命令挂起当前计算并把控制权交还给调用者A表示绑定到本次计算的值。请注意这个Free构造有一个有趣的特性它在堆上编码递归而不是像经典函数调用那样在栈上编码递归。这提供了前面提到的栈安全性使得非常大的Free结构也能被安全地求值。对照 Cats 源码Free的三个构造子 正是Pure、Suspend与FlatMapped其中Suspend实际存放的是S[A]即文档中归纳定义的F[Free[F, A]]在单层上的简化final private[free] case class Pure[S[_], A](a: A) extends Free[S, A] final private[free] case class Suspend[S[_], A](a: S[A]) extends Free[S, A] final private[free] case class FlatMapped[S[_], B, C](c: Free[S, C], f: C Free[S, B]) extends Free[S, B]flatMap的实现Free.scala直接构造FlatMapped(this, f)并用注释说明所有左结合绑定都会被重新结合为右结合。Free的Monad实例catsFreeMonadForFree把pure与flatMap分别映射到这两个构造子并且是StackSafeMonad。For the very curious ones如果你去看 cats 中的实现你会看到Free[_]ADT 中还有另一个成员case class FlatMapped[S[_], B, C](c: Free[S, C], f: C Free[S, B]) extends Free[S, B]FlatMapped表示一次对子程序c的调用当c完成时它用c的结果调用函数f来继续计算。它实际上是Free结构的一个优化用于解决非常深的递归Free计算隐含的平方复杂度问题。这与反复向List[_]追加元素的问题完全相同随着操作序列变长一次贯穿结构的flatMap会越来越慢。有了FlatMappedFree变成右结合结构从而避免了平方复杂度。FreeT在构建 AST 时混入其他效应很多时候我们希望在构建 Free Monad 的语法树时穿插一些没有声明在 ADT 中的其他效应。FreeT解决了这个问题它允许我们混合构建 AST 的步骤与在其他基础单子中调用动作。从源码看FreeT是Free的单子变换器monad transformersealed abstract class FreeT[S[_], M[_], A] extends Product with Serializable它的Suspend节点FreeT.scala同时携带基础单子效应Mprivate[free] case class Suspend[S[_], M[_], A](a: M[Either[S[A], A]]) extends FreeT[S, M, A]即每个挂起点是一个M[Either[S[A], A]]Left表示一条 ADT 命令Right表示已经求值出的纯值。由此FreeT在每一步都可以选择是执行 ADT 命令还是直接执行基础单子M中的操作。文档还说明FreeT 的栈安全基于 Phil Freeman 的论文Stack Safety for Free其 Scala 实现源自 Scalaz 的FreeT。下面是一个基础的控制台应用示例当用户输入文本时我们用独立的State单子记录用户输入了什么。在这个例子中FreeT为我们提供了把含义denotation委托给State单子的选择这比在我们自己的 ADT 里模拟State操作具有更强的等式保证equational guarantees。import cats.free._ import cats._ import cats.data._ /* A base ADT for the user interaction without state semantics */ sealed abstract class Teletype[A] extends Product with Serializable final case class WriteLine(line : String) extends Teletype[Unit] final case class ReadLine(prompt : String) extends Teletype[String] type TeletypeT[M[_], A] FreeT[Teletype, M, A] type Log List[String] type TeletypeState[A] State[List[String], A] /** Teletype smart constructors */ object TeletypeOps { def writeLine(line : String) : TeletypeT[TeletypeState, Unit] FreeT.liftFTeletype, TeletypeState, Unit) def readLine(prompt : String) : TeletypeT[TeletypeState, String] FreeT.liftFTeletype, TeletypeState, String) def log(s : String) : TeletypeT[TeletypeState, Unit] FreeT.liftTTeletype, TeletypeState, Unit) } def program : TeletypeT[TeletypeState, Unit] { for { userSaid - TeletypeOps.readLine(whats up?!) _ - TeletypeOps.log(suser said : $userSaid) _ - TeletypeOps.writeLine(thanks, see you soon!) } yield () } def interpreter new (Teletype ~ TeletypeState) { def applyA : TeletypeState[A] { fa match { case ReadLine(prompt) println(prompt) val userInput hanging in here //scala.io.StdIn.readLine() StateT.pure[Eval, List[String], A](userInput) case WriteLine(line) StateT.pure[Eval, List[String], A](println(line)) } } } import TeletypeOps._ val state program.foldMap(interpreter) val initialState Nil val (stored, _) state.run(initialState).value这里的两个操作符值得对照源码理解FreeT.liftF把S[A]命令提升为Suspend(M.pure(Left(value)))即这是一条 ADT 命令FreeT.liftT把M[A]效应直接提升为Suspend(M.map(value)(Right(_)))即直接执行基础单子动作。所以在同一个 for-comprehension 里readLine/writeLine走 ADT 解释器而log直接以State效应执行——这正是 FreeT交错构建能力的体现。运行后stored是经过log累积的日志列表例如List(user said : hanging in here)。另一个例子是FreeT与上下文Ctx的基础用法为Ctx提供Try解释器并组合OptionT以减少样板代码import cats.free._ import cats._ import cats.data._ import cats.syntax.all._ import scala.util.Try sealed trait Ctx[A] case class Action(value: Int) extends Ctx[Int] def op1: FreeT[Ctx, Option, Int] FreeT.liftFCtx, Option, Int) def op2: FreeT[Ctx, Option, Int] FreeT.liftTCtx, Option, Int) def op3: FreeT[Ctx, Option, Int] FreeT.pureCtx, Option, Int val opComplete: FreeT[Ctx, Option, Int] for { a - op1 b - op2 c - op3 } yield a b c /* Our interpreters */ type OptTry[A] OptionT[Try, A] def tryInterpreter: Ctx ~ OptTry new (Ctx ~ OptTry) { def applyA: OptTry[A] { fa match { case Action(value) OptionT.liftF(Try(value)) } } } def optTryLift: Option ~ OptTry new (Option ~ OptTry) { def applyA: OptTry[A] { fa match { case Some(value) OptionT(Try(Option(value))) case None OptionT.none } } } val hoisted opComplete.hoist(optTryLift) val evaluated hoisted.foldMap(tryInterpreter) val result evaluated.value这里展示了两条FreeT特有的操作链hoistFreeT.scala等价于mapK把基础单子从Option换成OptionT[Try, *]即把程序提升到更丰富的效应栈中foldMap用tryInterpreter把Ctx命令逐一解释为OptionT[Try, *]中的动作。最后result的类型为OptionT[Try, Int].value得到Try[Option[Int]]。注意三个op的构造方式也各不相同op1是 ADT 命令liftFop2是基础单子效应liftTop3是纯值pure——三者可以自由地编织进同一个 for-comprehension这正是 FreeT 相比 Free 的增量价值。关于FreeT的栈安全性FreeTSuite.scala 中也有直接验证5 万次flatMap的 FlatMap 栈安全测试、mapK与compile的栈安全测试均以 5 万步规模运行。更多阅读与后续工作文档还列出了Free[_]的许多值得关注的应用官方文档承诺未来会补充例如TrampolineOptionIterateeSource等等……以及Coyoneda Trick的讨论。其中Trampoline在 Cats 中已经可以直接使用它在 package.scala 中被定义为Free在Function0函子上的一种特化type Trampoline[A] Free[Function0, A]当你的计算不需要自定义 ADT只想获得栈安全的递归能力时Trampoline是最轻量的选择。相关的Coyoneda、Yoneda、Cofree、FreeApplicative、FreeInvariantMonoidal等类型也都位于 free/src/main/scala/cats/free/ 目录下并配有对应的测试套件可以作为进一步阅读的起点。总结通过本文你从零走完了一条完整的 Free Monad 实践路径概念Free Monad 是用任意Functor构造Monad的纯函数式构造核心是把计算表示为可重解释的数据五步法定义 ADT →type别名 →liftF智能构造器 → for-comprehension 程序 → 自然变换编译器 →foldMap执行解释器重定向同一个程序可用Id同步立即执行、State纯状态推进、Future异步、Either失败等不同容器解释实现程序与执行分离组合InjectKEitherK让多个 ADT 无缝组合成更复杂的程序且每个 ADT 保持独立的解释器栈安全Pure/Suspend/FlatMapped三节点结构把递归编码在堆上foldMap基于tailRecM实现 trampoliningFreeT在构建 AST 的同时通过liftT混入基础单子效应并通过hoist切换效应栈。掌握了这些模式你就能在 Cats 项目中用自由单子构建出一次定义、多端解释的领域语言把副作用隔离在解释器边界让业务逻辑保持纯粹、可测试、可组合。赞分享后端【免费下载链接】catsLightweight, modular, and extensible library for functional programming.项目地址https://gitcode.com/gh_mirrors/ca/cats点击查看免费下载相关推荐java-design-patterns 组合子模式Combinator Pattern实战用函数组合构建可复用的文本查询 DSLjava design patterns 组合子模式Combinator Pattern实战用函数组合构建可复用的文本查询 DSL 组合子模式Combi示例工程教程Geyser扩展开发入门从零编写你的第一个插件Geyser扩展开发入门从零编写你的第一个插件 什么是Geyser扩展 Geyser作为连接Minecraft: Java版和基岩版的桥梁提供了强大的扩展系后端FP in Scala Free Monad构建可组合的领域特定语言FP in Scala Free Monad构建可组合的领域特定语言 Free Monad 是函数式编程中一个强大的抽象它允许我们构建可组合的领域特定语言示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/12 20:09:01 · 阅读 1.2k Cats Free Monad 实战指南：用嵌入式 DSL 构建可组合、可重定向的纯函数式程序
后端【免费下载链接】catsLightweight, modular, and extensible library for functional programming.项目地址https://gitcode.com/gh_mirrors/ca/cats点击查看免费下载本文是 Cats 函数式编程库中cats-free模块的完整技术指南。自由单子Free Monad是一种从任意Functor构造出Monad的通用构造它允许你把程序当作纯数据来表示、组合与重解释先构建语法树再通过自然变换把它编译到任意目标解释器执行。读完本文你将掌握 Free Monad 的五大核心能力——把有状态计算表示为数据、栈安全地运行递归计算、构建嵌入式 DSL、用自然变换重定向计算到不同解释器以及用FreeT在构建 AST 的同时混入其他单子效应并能在真实项目中落地这些模式。本文全部内容基于 Cats 仓库中的官方 Free Monad 文档并辅以 Free.scala、FreeT.scala、InjectK.scala、EitherK.scala 等源码实现与测试用例作为佐证。什么是 Free Monad一个自由单子free monad是一种构造它允许你从任意Functor构建出一个Monad。和其他单子一样它是一种表示与操作计算的纯函数式方式。具体来说自由单子提供了以下实用能力将有状态的计算表示为数据并在之后运行它栈安全地运行递归计算构建嵌入式 DSL领域特定语言Domain-Specific Language使用自然变换natural transformation将计算重定向到另一个解释器。在 Cats 中表示自由单子的类型简写为Free[_]。从源码结构看Free的定义位于 free/src/main/scala/cats/free/Free.scala其核心注释明确写道A free operational monad for some functorS即针对某个函子S的自由操作单子并且绑定操作使用堆而非栈来完成从而实现尾调用消除。在 Cats 中表示自由单子的类型简写为Free[_]。使用 Free Monad添加依赖如果你想使用 Cats 的自由单子需要为项目添加cats-free模块的库依赖。在 Cats 仓库中cats-free模块在 build.sbt 中定义为跨平台项目JSPlatform / JVMPlatform / NativePlatformlazy val free crossProject(JSPlatform, JVMPlatform, NativePlatform) .crossType(CrossType.Pure) .dependsOn(core, tests % test-internal - test) .settings(moduleName : cats-free, name : Cats Free)在你的项目中通常只需要引入以 sbt 为例libraryDependencies org.typelevel %% cats-free % versioncats-free依赖cats-core包含Free、FreeT、Trampoline、Coyoneda等核心类型位于 free/src/main/scala/cats/free/。理解自由单子最好的方式是在实际代码中观察它——下面我们就用它来创建一个嵌入式 DSL。如果你对自由单子背后的范畴论理论感兴趣可以直接跳到文末的 理论章节。实战用 Free[_] 构建键值存储 DSL研究你的主题假设我们要为一个键值存储key-value store创建 DSL希望对键做三件事put将一个value关联到它的key存入存储get根据key从存储中取出valuedelete根据key从存储中删除value。我们的构想是用嵌入式 DSL 把这一系列操作写成一段程序编译这段程序最后执行它来真正地与键值存储交互。例如put(toto, 3) get(toto) // returns 3 delete(toto)同时我们希望计算被表示为纯的、不可变的值创建程序与执行程序分离能够支持多种不同的执行方式。研究你的语法与键值存储交互共有 3 条命令Put把一个值与一个键关联后存入存储Get根据键把关联的值从存储中取出Delete根据键把值从存储中删除。创建表示语法的 ADTADT 是Algebraic Data Type代数数据类型的缩写。在此语境下它指一组封闭的类型集合可以组合出复杂、递归的值。我们需要创建一个 ADT 来表示键值操作sealed trait KVStoreA[A] case class PutT extends KVStoreA[Unit] case class GetT extends KVStoreA[Option[T]] case class Delete(key: String) extends KVStoreA[Unit]注意这里每个 case class 都带有一个类型参数AKVStoreA[A]它表示这条操作执行成功后的返回类型Put和Delete返回UnitGet返回Option[T]。这个类型参数正是 Free Monad 能够把命令序列缝合成单子流程的关键——每个命令的返回类型会成为下一条命令的输入。释放Free你的 ADT把 ADT解放成 Free Monad 需要五个基本步骤创建基于Free[_]与KVStoreA[_]的类型使用liftF为KVStore[_]创建智能构造器smart constructors用键值 DSL 操作构建一个程序为 DSL 操作的程序构建一个编译器执行编译后的程序。1. 创建基于 ADT 的 Free 类型import cats.free.Free type KVStore[A] Free[KVStoreA, A]这里KVStore[A]就是Free[KVStoreA, A]的别名外层函子为KVStoreA最终计算结果类型为A。2. 使用 liftF 创建智能构造器这些方法会让 DSL 的使用体验好得多并把KVStoreA[_]的值提升到KVStore[_]单子中注意第二个类型参数少了字母 A。import cats.free.Free.liftF // Put returns nothing (i.e. Unit). def putT: KVStore[Unit] liftFKVStoreA, Unit) // Get returns a T value. def getT: KVStore[Option[T]] liftF[KVStoreA, Option[T]](GetT) // Delete returns nothing (i.e. Unit). def delete(key: String): KVStore[Unit] liftF(Delete(key)) // Update composes get and set, and returns nothing. def updateT: KVStore[Unit] for { vMaybe - getT _ - vMaybe.map(v putT)).getOrElse(Free.pure(())) } yield ()从源码看Free.liftF的实现极其简单def liftF[F[_], A](value: F[A]): Free[F, A] Suspend(value)它只是把F[A]包进Suspend节点。update展示了 Free Monad 的灵活之处get返回KVStore[Option[T]]借助Option的map/getOrElse可以优雅地处理键不存在的分支并用Free.pure(())作为空操作。3. 构建程序Program现在我们已经能构造KVStore[_]值可以用for-comprehension写出程序def program: KVStore[Option[Int]] for { _ - put(wild-cats, 2) _ - updateInt) _ - put(tame-cats, 5) n - getInt _ - delete(tame-cats) } yield n这看起来像是单子式流程但注意它实际上只是构建了一个递归数据结构用来表示操作序列。程序在构建阶段不产生任何执行效果。4. 为程序编写编译器Compiler现在你应该理解了Free[_]用来创建嵌入式 DSL。单独看这个 DSL 只表示一个操作序列由递归数据结构定义它本身不产生任何东西。Free[_]是你编程语言内部的编程语言所以和任何编程语言一样我们需要把抽象语言编译成有效的语言然后运行它。为此我们使用类型容器之间的自然变换。自然变换作用于F[_]和G[_]这样的类型之间这个特定的变换写作FunctionK[F, G]或使用符号别名F ~ G。在我们的例子中用一个简单的可变Map来表示键值存储import cats.arrow.FunctionK import cats.{Id, ~} import scala.collection.mutable // the program will crash if a type is incorrectly specified. def impureCompiler: KVStoreA ~ Id new (KVStoreA ~ Id) { // a very simple (and imprecise) key-value store val kvs mutable.Map.empty[String, Any] def applyA: Id[A] fa match { case Put(key, value) println(sput($key, $value)) kvs(key) value () case Get(key) println(sget($key)) kvs.get(key).asInstanceOf[A] case Delete(key) println(sdelete($key)) kvs.remove(key) () } }请注意这个impureCompiler是不纯的——它修改了kvs并且用println产生了日志输出。函数式编程的全部目的不是禁止副作用而是把副作用推到系统的边界以已知且可控的方式处理它们。Id[_]表示最简单的类型容器类型本身。因此Id[Int]就是Int。这意味着我们的程序会立即执行并阻塞直到最终值返回。然而我们很容易使用其他类型容器来获得不同的行为例如Future[_]异步计算List[_]收集多个结果Option[_]支持可选结果Either[E, *]支持失败一个伪随机单子支持不确定性等等……这种换一个解释器的能力正是 Free Monad 的核心价值同样的程序数据可以在不同语义下运行而程序本身无需任何修改。5. 运行你的程序最后一步自然是编译之后运行程序。Free[_]只是一个递归结构可以看作产生其他操作的操作序列。在这方面它与List[_]类似我们常用折叠如foldRight从列表中获得单个值——折叠遍历这个结构并合并其内容。运行Free[_]的思路完全相同折叠递归结构具体方式为消费每个操作用impureCompiler把操作编译到有效语言中如有副作用则应用它计算下一个操作递归继续直到到达Pure状态返回它。这个操作称为Free.foldMapfinal def foldMap[M[_]](f: FunctionK[S,M])(M: Monad[M]): M[A] ...M必须是一个Monad才能被展平著名的Monad之下的幺半群特质。由于Id是Monad我们可以使用foldMap。用之前的impureCompiler运行你的Freeval result: Option[Int] program.foldMap(impureCompiler)foldMap的一个重要特性是它的栈安全性stack-safety。它在栈上评估计算的每一步然后退栈并重新开始。这个过程称为trampolining蹦床。只要你的自然变换是栈安全的foldMap就永远不会栈溢出。蹦床是堆密集型的但栈安全性提供了使用Free[_]处理数据密集型任务以及流等无限进程所需的可靠性。从源码看Free.foldMap正是通过M.tailRecM实现栈安全的final def foldMap[M[_]](f: FunctionK[S, M])(implicit M: Monad[M]): M[A] M.tailRecM(this)(_.step match { case Pure(a) M.pure(Right(a)) case Suspend(sa) M.map(f(sa))(Right(_)) case FlatMapped(c, g) M.map(c.foldMap(f))(cc Left(g(cc))) })每次循环要么返回Right结果就绪要么返回Left继续计算把下一步做什么以堆上的值传递从而避免 JVM 调用栈的深度增长。6. 使用纯编译器可选前面的例子使用了带副作用的自然变换。这可行但你可能更愿意以更纯的方式折叠你的Free。State 数据结构可以在不可变Map中跟踪程序状态完全避免可变性import cats.data.State type KVStoreState[A] State[Map[String, Any], A] val pureCompiler: KVStoreA ~ KVStoreState new (KVStoreA ~ KVStoreState) { def applyA: KVStoreState[A] fa match { case Put(key, value) State.modify(_.updated(key, value)) case Get(key) State.inspect(_.get(key).asInstanceOf[A]) case Delete(key) State.modify(_ - key) } }可以看到我们又一次遇到了 Scala 的模式匹配受 JVM 类型擦除限制的地方但克服起来并不难。运行val result: (Map[String, Any], Option[Int]) program.foldMap(pureCompiler).run(Map.empty).value这里foldMap把KVStoreA的每条操作映射为一次State变换最终通过.run(Map.empty).value得到最终状态Map[String, Any]与结果Option[Int]的二元组——全程没有任何可变状态。相比impureCompiler纯编译器把程序的状态推进完全纳入类型系统天然可重放、可测试。栈安全的源码级验证自由单子栈安全的说法并非空谈FreeSuite.scala 中有大量直接测试toString 是栈安全的对Free.pureList, Int连续做100 万次map仍能正常输出tailRecM是栈安全的通过tailRecM递归 5 万次foldMap是栈安全的一个递归 1 万层的程序用Id解释器执行后正确返回10000.runTailRec与.run各 10 万次递归的flatMap链都能正常求值。这些测试共同印证了Free把递归编码在堆上而非栈上的设计结论。组合 Free Monads 的 ADT真实世界的应用常常需要组合不同的代数algebra。Swierstra 在Data types à la carte中描述的injection 类型类让我们可以在Free的上下文中组合不同的代数——在 Cats 中它就是InjectK位于 core/src/main/scala/cats/InjectK.scala在 Cats 1.0 之前称为Inject。让我们看一个简单例子把两个互不相关的 ADT 组合成一个EitherK从而形成更复杂的程序。import cats.data.EitherK import cats.free.Free import cats.{Id, InjectK, ~} import scala.collection.mutable.ListBuffer定义两个 ADT/* Handles user interaction */ sealed trait Interact[A] case class Ask(prompt: String) extends Interact[String] case class Tell(msg: String) extends Interact[Unit] /* Represents persistence operations */ sealed trait DataOp[A] case class AddCat(a: String) extends DataOp[Unit] case class GetAllCats() extends DataOp[List[String]]ADT 定义好后我们可以正式声明一个Free程序就是其各代数algebra的EitherK。type CatsApp[A] EitherK[DataOp, Interact, A]从源码看EitherK的底层就是scala.util.Either的类型构造器版本final case class EitherK[F[_], G[_], A](run: Either[F[A], G[A]])而InjectK提供一对互逆的注入/投影函数abstract class InjectK[F[_], G[_]] { def inj: FunctionK[F, G] // 从 F 无损注入到 G def prj: FunctionK[G, λ[α Option[F[α]]]] // 部分逆从 G 投影回 F }注入是不丢失任何信息的函子变换对于每个ga: G[A]至多有一个fa: F[A]满足inj(fa) ga。为了利用单子组合我们使用智能构造器把每个代数提升到Free上下文class Interacts[F[_]](implicit I: InjectK[Interact, F]) { def tell(msg: String): Free[F, Unit] Free.liftInjectF) def ask(prompt: String): Free[F, String] Free.liftInjectF) } object Interacts { implicit def interacts[F[_]](implicit I: InjectK[Interact, F]): Interacts[F] new Interacts[F] } class DataSource[F[_]](implicit I: InjectK[DataOp, F]) { def addCat(a: String): Free[F, Unit] Free.liftInjectF) def getAllCats: Free[F, List[String]] Free.liftInjectF) } object DataSource { implicit def dataSource[F[_]](implicit I: InjectK[DataOp, F]): DataSource[F] new DataSource[F] }这里的Free.liftInject[F]对应于源码中Free.liftInject在给定InjectK[F, G]的前提下把F[A]注入到G[A]后再liftF进 Freedef liftInject[G[_]]: FreeLiftInjectKPartiallyApplied[G] ... // 内部实现 // Free.liftF(I.inj(fa)) // I: InjectK[F, G]现在 ADT 可以轻松组合并在单子上下文中自然地交错使用def program(implicit I : Interacts[CatsApp], D : DataSource[CatsApp]): Free[CatsApp, Unit] { import I._, D._ for { cat - ask(Whats the kittys name?) _ - addCat(cat) cats - getAllCats _ - tell(cats.toString) } yield () }最后为每个 ADT 写一个解释器并用FunctionK组合成EitherK的解释器以便编译并应用到我们的Free程序object ConsoleCatsInterpreter extends (Interact ~ Id) { def applyA i match { case Ask(prompt) println(prompt) readLine() case Tell(msg) println(msg) } } object InMemoryDatasourceInterpreter extends (DataOp ~ Id) { private[this] val memDataSet new ListBuffer[String] def applyA fa match { case AddCat(a) memDataSet.append(a); () case GetAllCats() memDataSet.toList } } val interpreter: CatsApp ~ Id InMemoryDatasourceInterpreter or ConsoleCatsInterpreterInMemoryDatasourceInterpreter or ConsoleCatsInterpreter正是利用FunctionK的组合能力把两个分别针对DataOp与Interact的解释器合并成一个针对EitherK[DataOp, Interact, *]的解释器or即FunctionK.or对EitherK的左右两侧分别派发。现在运行我们的程序——提示输入时键入 snugglesimport DataSource._, Interacts._ val evaled: Unit program.foldMap(interpreter)执行时ask打印提示并从控制台读取名字addCat存入内存列表getAllCats取回列表tell打印结果——控制台上会看到类似List(snuggles)的输出。组合的关键意义在于Free程序本身完全不知道解释器的存在。你可以为同一组 ADT 编写任意多个解释器内存版、数据库版、测试桩版程序数据一字不改。For the curious ones: Free 在理论上是什么从数学角度讲一个自由单子至少在编程语言语境下是某个遗忘函子forgetful functor的左伴随构造该遗忘函子的定义域是 Monads 范畴陪域是 Endofunctors 范畴。是不是有点懵具体来说它只是一个巧妙的构造允许我们从任意函子构建一个非常简单的 Monad。上述遗忘函子取出一个Monad之后会遗忘其 monadic 部分例如flatMap函数遗忘其 pointed 部分例如pure函数保留其 functor 部分例如map函数。通过反转所有箭头来构造左伴随我们推断出自由单子基本上是这样一种构造它接受一个函子加上 pointed 部分例如pure加上 monadic 行为例如flatMap。在实现层面为了从函子构建单子我们使用下面这个经典的归纳定义sealed abstract class Free[F[_], A] case class Pure[F[_], A](a: A) extends Free[F, A] case class Suspend[F[_], A](a: F[Free[F, A]]) extends Free[F, A]这推广了不动点函子的概念。在这个表示中Pure从一个A值构建Free实例它物化了pure函数Suspend通过把F应用于先前的Free来构建新的Free它物化了flatMap函数。于是一个典型的Free结构可能长这样Suspend(F(Suspend(F(Suspend(F(....(Pure(a))))))))Free是一个递归结构。它把F[A]中的A当作递归的载体carrier以Pure作为终止元素。从计算的角度看Free递归结构可以看作操作序列Pure返回一个A值并结束整个计算Suspend是一个续体continuation它用挂起函子F例如可以表示一条命令挂起当前计算并把控制权交还给调用者A表示绑定到本次计算的值。请注意这个Free构造有一个有趣的特性它在堆上编码递归而不是像经典函数调用那样在栈上编码递归。这提供了前面提到的栈安全性使得非常大的Free结构也能被安全地求值。对照 Cats 源码Free的三个构造子 正是Pure、Suspend与FlatMapped其中Suspend实际存放的是S[A]即文档中归纳定义的F[Free[F, A]]在单层上的简化final private[free] case class Pure[S[_], A](a: A) extends Free[S, A] final private[free] case class Suspend[S[_], A](a: S[A]) extends Free[S, A] final private[free] case class FlatMapped[S[_], B, C](c: Free[S, C], f: C Free[S, B]) extends Free[S, B]flatMap的实现Free.scala直接构造FlatMapped(this, f)并用注释说明所有左结合绑定都会被重新结合为右结合。Free的Monad实例catsFreeMonadForFree把pure与flatMap分别映射到这两个构造子并且是StackSafeMonad。For the very curious ones如果你去看 cats 中的实现你会看到Free[_]ADT 中还有另一个成员case class FlatMapped[S[_], B, C](c: Free[S, C], f: C Free[S, B]) extends Free[S, B]FlatMapped表示一次对子程序c的调用当c完成时它用c的结果调用函数f来继续计算。它实际上是Free结构的一个优化用于解决非常深的递归Free计算隐含的平方复杂度问题。这与反复向List[_]追加元素的问题完全相同随着操作序列变长一次贯穿结构的flatMap会越来越慢。有了FlatMappedFree变成右结合结构从而避免了平方复杂度。FreeT在构建 AST 时混入其他效应很多时候我们希望在构建 Free Monad 的语法树时穿插一些没有声明在 ADT 中的其他效应。FreeT解决了这个问题它允许我们混合构建 AST 的步骤与在其他基础单子中调用动作。从源码看FreeT是Free的单子变换器monad transformersealed abstract class FreeT[S[_], M[_], A] extends Product with Serializable它的Suspend节点FreeT.scala同时携带基础单子效应Mprivate[free] case class Suspend[S[_], M[_], A](a: M[Either[S[A], A]]) extends FreeT[S, M, A]即每个挂起点是一个M[Either[S[A], A]]Left表示一条 ADT 命令Right表示已经求值出的纯值。由此FreeT在每一步都可以选择是执行 ADT 命令还是直接执行基础单子M中的操作。文档还说明FreeT 的栈安全基于 Phil Freeman 的论文Stack Safety for Free其 Scala 实现源自 Scalaz 的FreeT。下面是一个基础的控制台应用示例当用户输入文本时我们用独立的State单子记录用户输入了什么。在这个例子中FreeT为我们提供了把含义denotation委托给State单子的选择这比在我们自己的 ADT 里模拟State操作具有更强的等式保证equational guarantees。import cats.free._ import cats._ import cats.data._ /* A base ADT for the user interaction without state semantics */ sealed abstract class Teletype[A] extends Product with Serializable final case class WriteLine(line : String) extends Teletype[Unit] final case class ReadLine(prompt : String) extends Teletype[String] type TeletypeT[M[_], A] FreeT[Teletype, M, A] type Log List[String] type TeletypeState[A] State[List[String], A] /** Teletype smart constructors */ object TeletypeOps { def writeLine(line : String) : TeletypeT[TeletypeState, Unit] FreeT.liftFTeletype, TeletypeState, Unit) def readLine(prompt : String) : TeletypeT[TeletypeState, String] FreeT.liftFTeletype, TeletypeState, String) def log(s : String) : TeletypeT[TeletypeState, Unit] FreeT.liftTTeletype, TeletypeState, Unit) } def program : TeletypeT[TeletypeState, Unit] { for { userSaid - TeletypeOps.readLine(whats up?!) _ - TeletypeOps.log(suser said : $userSaid) _ - TeletypeOps.writeLine(thanks, see you soon!) } yield () } def interpreter new (Teletype ~ TeletypeState) { def applyA : TeletypeState[A] { fa match { case ReadLine(prompt) println(prompt) val userInput hanging in here //scala.io.StdIn.readLine() StateT.pure[Eval, List[String], A](userInput) case WriteLine(line) StateT.pure[Eval, List[String], A](println(line)) } } } import TeletypeOps._ val state program.foldMap(interpreter) val initialState Nil val (stored, _) state.run(initialState).value这里的两个操作符值得对照源码理解FreeT.liftF把S[A]命令提升为Suspend(M.pure(Left(value)))即这是一条 ADT 命令FreeT.liftT把M[A]效应直接提升为Suspend(M.map(value)(Right(_)))即直接执行基础单子动作。所以在同一个 for-comprehension 里readLine/writeLine走 ADT 解释器而log直接以State效应执行——这正是 FreeT交错构建能力的体现。运行后stored是经过log累积的日志列表例如List(user said : hanging in here)。另一个例子是FreeT与上下文Ctx的基础用法为Ctx提供Try解释器并组合OptionT以减少样板代码import cats.free._ import cats._ import cats.data._ import cats.syntax.all._ import scala.util.Try sealed trait Ctx[A] case class Action(value: Int) extends Ctx[Int] def op1: FreeT[Ctx, Option, Int] FreeT.liftFCtx, Option, Int) def op2: FreeT[Ctx, Option, Int] FreeT.liftTCtx, Option, Int) def op3: FreeT[Ctx, Option, Int] FreeT.pureCtx, Option, Int val opComplete: FreeT[Ctx, Option, Int] for { a - op1 b - op2 c - op3 } yield a b c /* Our interpreters */ type OptTry[A] OptionT[Try, A] def tryInterpreter: Ctx ~ OptTry new (Ctx ~ OptTry) { def applyA: OptTry[A] { fa match { case Action(value) OptionT.liftF(Try(value)) } } } def optTryLift: Option ~ OptTry new (Option ~ OptTry) { def applyA: OptTry[A] { fa match { case Some(value) OptionT(Try(Option(value))) case None OptionT.none } } } val hoisted opComplete.hoist(optTryLift) val evaluated hoisted.foldMap(tryInterpreter) val result evaluated.value这里展示了两条FreeT特有的操作链hoistFreeT.scala等价于mapK把基础单子从Option换成OptionT[Try, *]即把程序提升到更丰富的效应栈中foldMap用tryInterpreter把Ctx命令逐一解释为OptionT[Try, *]中的动作。最后result的类型为OptionT[Try, Int].value得到Try[Option[Int]]。注意三个op的构造方式也各不相同op1是 ADT 命令liftFop2是基础单子效应liftTop3是纯值pure——三者可以自由地编织进同一个 for-comprehension这正是 FreeT 相比 Free 的增量价值。关于FreeT的栈安全性FreeTSuite.scala 中也有直接验证5 万次flatMap的 FlatMap 栈安全测试、mapK与compile的栈安全测试均以 5 万步规模运行。更多阅读与后续工作文档还列出了Free[_]的许多值得关注的应用官方文档承诺未来会补充例如TrampolineOptionIterateeSource等等……以及Coyoneda Trick的讨论。其中Trampoline在 Cats 中已经可以直接使用它在 package.scala 中被定义为Free在Function0函子上的一种特化type Trampoline[A] Free[Function0, A]当你的计算不需要自定义 ADT只想获得栈安全的递归能力时Trampoline是最轻量的选择。相关的Coyoneda、Yoneda、Cofree、FreeApplicative、FreeInvariantMonoidal等类型也都位于 free/src/main/scala/cats/free/ 目录下并配有对应的测试套件可以作为进一步阅读的起点。总结通过本文你从零走完了一条完整的 Free Monad 实践路径概念Free Monad 是用任意Functor构造Monad的纯函数式构造核心是把计算表示为可重解释的数据五步法定义 ADT →type别名 →liftF智能构造器 → for-comprehension 程序 → 自然变换编译器 →foldMap执行解释器重定向同一个程序可用Id同步立即执行、State纯状态推进、Future异步、Either失败等不同容器解释实现程序与执行分离组合InjectKEitherK让多个 ADT 无缝组合成更复杂的程序且每个 ADT 保持独立的解释器栈安全Pure/Suspend/FlatMapped三节点结构把递归编码在堆上foldMap基于tailRecM实现 trampoliningFreeT在构建 AST 的同时通过liftT混入基础单子效应并通过hoist切换效应栈。掌握了这些模式你就能在 Cats 项目中用自由单子构建出一次定义、多端解释的领域语言把副作用隔离在解释器边界让业务逻辑保持纯粹、可测试、可组合。赞分享后端【免费下载链接】catsLightweight, modular, and extensible library for functional programming.项目地址https://gitcode.com/gh_mirrors/ca/cats点击查看免费下载相关推荐java-design-patterns 组合子模式Combinator Pattern实战用函数组合构建可复用的文本查询 DSLjava design patterns 组合子模式Combinator Pattern实战用函数组合构建可复用的文本查询 DSL 组合子模式Combi示例工程教程Geyser扩展开发入门从零编写你的第一个插件Geyser扩展开发入门从零编写你的第一个插件 什么是Geyser扩展 Geyser作为连接Minecraft: Java版和基岩版的桥梁提供了强大的扩展系后端FP in Scala Free Monad构建可组合的领域特定语言FP in Scala Free Monad构建可组合的领域特定语言 Free Monad 是函数式编程中一个强大的抽象它允许我们构建可组合的领域特定语言示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考