尧图网站建设 
1. 为什么“身体里长着自己”的类型是硬需求1.1 树、JSON、文件系统结构递归到处都是我第一次对 Scala 递归类型产生强烈兴趣是因为一个看起来非常普通的任务用 Scala 写一个 JSON 解析器。JSON 的语法结构是天然自指的一个 array 的元素还是 json一个 object 的字段值还是 json整个数据定义里反复出现自己的名字。如果类型系统不能表达“这个类型里面包含自己”那写出来的代码就只能在运行时靠各种比较粗糙的手段兜底。树结构更是如此文件系统目录、表达式语法树、组织结构、依赖关系图全是同一个模式我定义某种形态的节点节点再嵌入同样形态的节点唯一的不同只是具体业务数据的形态有差异。递归类型就是那类专门描述“自指涉数据结构”的工具。它让编译器知道这个类型里面真的可以有同类型的子节点并且这种嵌套可以无限延展下去一直到某个明确的终止条件为止。不只是工程语言数学里早就这么干了自然数可以定义为零或某个自然数的后继列表可以定义为空或“一个元素加上一个列表”。递归类型不是某个特定语言的语法糖而是对“结构嵌套”这种现实需求的直接建模。1.2 不用递归类型时项目会滑向哪里有个很典型的反面模式你多半见过业务里要保存一棵树于是有人图省事直接用Map[String, Any]来表示节点。键是字段名值是基本类型或者子节点列表。第一眼看起来灵活项目推进到一个阶段就会开始出问题。取值要一层层做asInstanceOf子节点类型稍微变一下处理代码就要改一片很多错误不是在编译时暴露的而是在线上运行时变成异常。如果数据形状更复杂一点比如节点可能分为“普通节点”“叶子节点”和“带元数据的节点”这类方案基本会退化成一大片手工类型判断。更难受的是编辑器跳转不灵重构不敢做团队新成员看半天也不知道一个节点到底能装什么。递归类型解决的不是“能不能写出来”的问题而是“类型约束能不能在编译期帮你兜住”的问题。用 ADT 表达自指涉结构所有分支都写在同一处模式匹配时编译器会提醒你哪些情况没处理改动分支时也能通过警告快速发现受影响的调用点。1.3 一门语言的类型系统本质上是在为“结构真相”背书递归类型之所以值得认真掌握是因为它把“结构上允许什么”这件事直接提升到了类型层。我一直强调一个观点类型定义就是业务设计文档而且是会被编译器执行的文档。当你写下case class Folder(name: String, children: List[Folder])时你其实是在声明一条铁律文件夹的 children 也是一个文件夹。所有递归函数无论深度遍历还是规模统计都建立在这个不动点上。反过来只要破坏这种嵌套关系比如塞一个字符串进去编译器立刻拒绝。这种能力在 Scala 3 的 enum 上体现得特别清晰。enum 的分支集合是封闭的编译器可以拿着模式匹配里的每个分支去核对定义漏了哪个就是警示。这种穷尽性检查对自指涉结构价值极大因为递归结构的遍历代码通常是一连串 match 分支稍不留神就会漏掉一个递归子结构编译器能帮你把漏分支的隐患在产生 bug 之前就标出来。2. 从 Scala 2 到 Scala 3递归类型的主要写法2.1 先备好运行环境Linux 上跑起来很简单后面所有例子都用 Scala 3 语法运行环境其实很轻。在 Linux 上最省事的是先装好 JDK 17然后用 SDKMAN 或直接下载 scala-cli。scala-cli 非常适合这种纯文件测试写一个.scala文件跑一句scala-cli run demo.scala就能看到结果。# 建议先安装 SDKMAN再装 scala-cli 和 scala 3 sdk install java 17-tem sdk install scala sdk install scalacli然后新建一个文件比如RecTypeDemo.scalamain def demo(): Unit println(recursive type demo ready)命令行执行scala-cli run RecTypeDemo.scala看到输出说明环境就绪。日常练习不需要上重型构建工具等代码多起来再引入 sbt 也不迟。这个工作流在 Linux 服务器上同样顺手没有图形界面也没关系写的 Scala 代码和你在 IDE 里看到的完全一致。2.2 Scala 2 经典流派sealed trait 加 case classScala 2 时代表达自指涉结构的主流方式是 sealed trait 加上一堆 case class 子类。jargon 里常把这组东西叫 ADTAlgebraic Data Type代数数据类型。它为什么适合递归类型因为 trait 负责定义“总体形状”而每个子类负责一种具体构造形态构造形态里可以再次引用 trait 本身。以最经典的表达式树为例sealed trait Expr object Expr: case class Num(value: Int) extends Expr case class Add(left: Expr, right: Expr) extends Expr case class Mul(left: Expr, right: Expr) extends ExprAdd的两个字段类型还是Expr所以写出了表达式的无限嵌套。sealed 关键字限定了子类只能出现在同一个文件里这让编译器可以枚举所有分支模式匹配的穷尽性检查才能生效。只要有人改了Expr的分支所有遍历代码都可能出现编译警告这比运行时才发现要踏实太多。这种写法的好处是老项目迁移成本低Scala 2.13 和 Scala 3 都能跑。缺点是样板代码稍微多一点每个子类要写extends Expr定义 Enum 语义时不如 Scala 3 直接。2.3 Scala 3 流派enum 让递归分支更直观Scala 3 引入了真正的 enum写同样一套结构代码会更紧凑也更接近“节点只有这几种形态”的直觉enum Expr: case Num(value: Int) case Add(left: Expr, right: Expr) case Mul(left: Expr, right: Expr)分支直接缩进在 enum 内部递归引用Expr不会产生任何歧义。写遍历函数时分支名称携带构造参数模式匹配非常舒展def eval(expr: Expr): Int expr match case Expr.Num(value) value case Expr.Add(left, right) eval(left) eval(right) case Expr.Mul(left, right) eval(left) * eval(right)这段函数就是递归类型的标准搭档以递归定义为基础按分支遍历结构区分终止分支和递归展开分支再把子表达式结果合并起来。Scala 3 的 enum 还支持泛型和类型参数比如enum Tree[A]可以做多态递归树功能上没有短板。2.4 为什么type Expr List[Expr]是不成立的初学者经常会碰一个坎好像只要类型别名叫自己就行。比如写了type JsonNode Map[String, JsonNode]Scala 编译器会直接拒绝因为 type alias 不是真正的新类型它只是替换符号。编译器一旦展开别名看到的就是Map[String, Map[String, Map[String, ...]]]一个永远停不下来的展开过程于是报出循环引用错误。要表达递归结构必须有一个真名实姓的类或枚举类型作为递归入口case class、enum、trait 都可以唯独纯 type alias 不行。这背后的原因很有趣递归类型需要能判定“这个值到底长什么样”而真实类型必须有一个明确的构造点。case class 有运行时构造入口enum 有确定的 case 集合type alias 没有。理解这条边界能少踩很多“为什么我写的递归类型编译不过”的坑。3. 实操用递归类型写出真正能跑的自指涉结构3.1 定义 JSON AST每一层都由六个分支接管我常用 JSON 模型来演示递归类型设计因为它足够简单又覆盖了嵌套、列表、映射、终止分支这几种核心场景。用 Scala 3 定义enum Json: case JNull case JBool(value: Boolean) case JNumber(value: BigDecimal) case JString(value: String) case JArray(items: Vector[Json]) case JObject(fields: Map[String, Json])第一眼看过去JArray里的Vector[Json]是递归JObject里的Map[String, Json]也是递归。前者是“同结构可重复”后者是“通过键名引用自身”。这种定义把 JSON 的完整结构压缩在六行里比任何文档都精确。设计递归类型时我给自己定过一条规矩每个递归分支都必须有一个清晰的集合容器不要让单个字段以Option[Json]的形式玩花活。Option[Json]当然能表示可空字段但当数据变成深层嵌套时Option 套 Option 会让代码苦不堪言。更推荐的做法是让字段默认给一个空值比如JArray直接给空VectorJObject直接给空Map然后用分支本身表达语义递归深度就不容易失控。3.2 递归遍历函数match 分支就是结构的镜子定义完类型后遍历逻辑会显得几乎是自动生成的。比如写一个prettyPrint把 JSON 缩进打印出来def pretty(json: Json, indent: Int 0): String val pad * indent json match case Json.JNull pad null case Json.JBool(b) pad b.toString case Json.JNumber(n) pad n.toString case Json.JString(s) pad \ s \ case Json.JArray(items) items.map(item pretty(item, indent 1)).mkString(pad [\n, ,\n, \n pad ]) case Json.JObject(fields) fields .map { case (k, v) pad \ k \: pretty(v, indent 2) } .mkString(pad {\n, ,\n, \n pad })模式匹配的每个分支恰好对应 enum 定义里的每个 case。这里是递归类型的另一个魅力你不用专门写一个“判断当前节点属于什么类型”的调度器模式匹配天然按类型分发。漏掉JNull编译器立刻标出 non-exhaustive warning新增一种 case所有 match 位置都会被警告逐个补上就行。3.3 文件系统目录树给递归节点配上名字和子节点再把递归类型用到更贴近系统编程的场景。文件目录是标准树目录套目录文件是叶子case class FsNode( name: String, isDirectory: Boolean, children: Vector[FsNode] Vector.empty )这个 case class 只有一个递归容器字段。它非常简洁但要注意一点当目录和文件的差异用一个布尔字段而非不同分支表达时遍历代码里不可避免要写if node.isDirectory。我并非反对这种方式只是提醒布尔字段分支会让类型模型的“分支语义”变弱不如 enum 清晰。做成完整 ADT 会更稳enum FsEntry: case Dir(name: String, children: Vector[FsEntry]) case File(name: String, sizeBytes: Long)这时递归类型跟业务语义彻底对齐只有 Dir 允许有子节点File 本身就是终止节点。随之而来的遍历函数只剩三种情况倒也能接受def totalSize(entry: FsEntry): Long entry match case FsEntry.File(name, size) size case FsEntry.Dir(name, children) children.map(totalSize).sum当递归分支和非递归分支被类型强制区分出来代码分支就不会出现“忘了处理文件节点”的尴尬。3.4 泛型递归LinkedList 与 Tree 的通用形态自指涉结构经常需要携带不同载荷这时要给递归类型加泛型参数。LinkedList 是经典enum LinkedList[A]: case Empty case Cons(head: A, tail: LinkedList[A]) def size[A](list: LinkedList[A]): Int list match case LinkedList.Empty 0 case LinkedList.Cons(h, t) 1 size(t)这里的递归点是tail: LinkedList[A]一旦给A换成具体类型整个链表的元素类型就固定下来。协变标注A是安全的因为我们只把A放在读取位置没有var head: A这类可变写入。递归类型跟泛型参数组合是常态JSON AST 里的Map[String, Json]本质上也是一种泛型递归只是容器换成 Map 而已。4. 循环引用、互递归类型和惰性求值4.1 类型递归和值递归要分清楚递归类型说的是“类型定义里包含自己”但是运行时能不能构造出循环引用是另一个层面的问题。最常见的例子是有向图节点 A 指向节点 BB 又指回 A。类型上两个节点都可以是Node。但如果按普通字段直接构造就会在初始化时遭遇“先有鸡还是先有蛋”的死结。Scala 的 lazy val 能化解这个死结。它把初始化推迟到第一次访问时让两个对象互相能看到对方同时形成循环引用。case class Node(name: String, neighbors: List[Node]) object Graph: lazy val a: Node Node(a, List(b)) lazy val b: Node Node(b, List(a))这里a定义里用了bb定义里用了a类型上两边都是Node值上靠 lazy 机制完成互相构造。这种写法适合表示不可变的循环引用结构比如状态机、依赖环、邻近关系。要注意的是打印这种结构会绕圈子不要指望toString能给出让人舒服的结果更别直接用递归函数去求“无限深图”的深度否则栈肯定爆。4.2 互递归类型两个类型互相引用对方自指涉数据结构不一定是单个类型绕回自己还可以是多个类型互相绕。编译器和类型检查器里非常常见语法树里的表达式和发展环境可以互相引用。简化一下是这样enum Expr: case Var(name: String) case Let(name: String, value: Expr, body: Expr) final case class Env(bindings: Map[String, EnvEntry]) enum EnvEntry: case Value(expr: Expr) case Scope(env: Env)Expr里出现EnvEntryEnvEntry里出现Expr。它们互为递归。Scala 允许这样的定义但要注意最好把它们放在同一个文件避免复杂包级循环。这种互递归结构如果换成接口加实现类写起来会散落很多而用 ADT 一口气列出来类型之间的引用关系一目了然。我个人体会是只要出现两个以上的互递归类型就应该把整个家族定义集中在一个文件里管理。类型本身是“结构真相”让真相集中在显眼处后续维护时打开一个文件就能看到全局。4.3 递归边界与 F-bounded 多态有些自指涉类型不是面向数据的而是面向操作约束的。比如想定义一个“可比较、且比较时只能与自身类型比较”的接口Scala 里常见写法是trait Comparable[T : Comparable[T]]: def compare(other: T): Int注意T : Comparable[T]这种递归边界让 T 必须是“实现了 Comparable[T] 的类型”。比如Person实现Comparable[Person]之后compare就只能接收Person不能拿Person和Company瞎比。这个模式叫 F-bounded 多态它是自指涉类型在类型参数上的一种递归表达。理解它对阅读泛型库源码非常有帮助。很多 Scala 类型类的设计都依赖这种“类型递归边界”Shapeless 的Generic[T]、Cats 的Show[T]虽然平常写法不直接自指但高级抽象里到处都是 T 与某个更高 kind 类型互相约束的影子。4.4 递归结构一定会遇到终止问题写递归函数时一句老话永远适用没有终止分支的递归不是数据结构是灾难。类型允许无限嵌套不意味着遍历就得无限跑而是要求遍历函数在每个分支上给出处理尤其是那个不再递归下去的终止分支。比如对Json求节点总数def count(json: Json): Int json match case Json.JNull | Json.JBool(_) | Json.JNumber(_) | Json.JString(_) 1 case Json.JArray(items) 1 items.map(count).sum case Json.JObject(fields) 1 fields.values.map(count).sum终止分支是那些不含子结构的叶子 case。漏掉任何一个叶子分支模式匹配会给出提醒漏掉递归分支可能直接导致栈溢出。判断递归函数是否健康就看每个递归调用的参数是不是都在向叶子结构收敛。这个判断应该成为条件反射。5. 实战排雷调试递归类型时踩过的坑5.1 “illegal cyclic reference”通常是类型标注缺失Scala 的类型推导虽然强大但碰到递归结构时编译器也需要更多线索。我见过不少编译报错报的是illegal cyclic reference第一反应以为递归类型写错了。其实很多时候不是类型定义错而是推导过程走进了死胡同。比如某段代码里写了一个返回自身的函数不给返回类型编译器猜不出来一个有限大小的类型签名就会拒绝。经验是递归函数务必显式标注返回类型。它不仅让代码可读也让编译器的推导路径短很多。一旦显式标注原本神秘的 cyclic reference 错误往往会变成普通类型不匹配立刻能看清是哪个字段塞错了。递归类型定义也同理宁可多写几行类型签名也绝不在模式匹配和递归调用里全靠推导。5.2 深递归导致 StackOverflow递归类型允许很深的结构但 JVM 的方法调用栈不是无限的。构造一个百万层的 JSON 数组再写递归count大概率会在某层栈溢出。这个问题不是类型系统错误而是运行时物理限制。处理方式有几种。最简单的是把递归转成尾递归并加上tailrec让编译器验证但很多递归结构天然不是尾递归比如遍历树时先处理左边再处理右边每次调完还有后续操作。这种场景可以用显式栈模拟递归def countIterative(json: Json): Int val stack scala.collection.mutable.Stack[Json](json) var total 0 while stack.nonEmpty do stack.pop() match case Json.JArray(items) items.foreach(stack.push) case Json.JObject(fields) fields.values.foreach(stack.push) case _ () total 1 total手动栈用循环替代递归深度不再受调用栈限制。自指涉结构深度比较依赖这个技巧值得熟练掌握。5.3 协变标注和不可变字段是递归类型的好朋友给递归类型加泛型参数时最常见的编译错误来自方差标注。如果写出enum Node[A] { case Cons(head: A, next: Node[A]) }可以编译但如果字段是可变的case class MutableNode[A](var next: Option[MutableNode[A]])再标记A编译器就会抗议因为var字段既是读出又是写入破坏了协变需要的“只读”约束。我踩过这种坑想让Node协变但又想保留可变 next 字段最后只能在两者之间取舍。真正适合协变的是不可变递归结构比如List[A]、Tree[A]可变结构就老老实实不标方差。这个约束不是烦人的限制它其实保证了类型安全否则一个Node[Dog]可能会在运行时被塞进Node[Animal]里。5.4 匹配警告一定要当回事Scala 编译器对 sealed trait 和 enum 的穷尽性检查非常用心。递归类型的遍历一旦漏分支通常闪一下 warning。它的语气很温和但我们不能把自己养成忽略 warning 的习惯。把漏掉的分支补上或者明确写出case _ 都是可以的选择但要刻意决定而不是放任不管。我习惯在构建配置里开启-Werror或者-Xfatal-warnings让 warning 直接变成 error。这样新增分支后所有受影响的递归遍历函数都会被编译错误点醒。第一次会觉着残酷但交付质量确实提高了没有一处递归分支能被悄悄遗忘。症状可能原因处理思路illegal cyclic reference递归函数缺返回类型或 type alias 直接自指给函数补显式类型把 alias 改成 case class / enumvariance 编译错误可变字段出现在递归泛型类型中改成不可变字段或去掉协变标注StackOverflow递归深度超过 JVM 栈容量改尾递归或改为显式栈循环non-exhaustive warning新增分支后遍历函数没更新逐个 match 补分支或统一生成默认分支启动后才报类型错误数据层用 Any 绕过类型检查改用完整 ADT尽早把结构交给编译器6. 设计递归类型的一页心得把“艺术与科学”落到实处回到标题里那个“艺术与科学”。科学的一面是类型规则明确递归边界、方差、穷尽性检查都有硬性的编译判断艺术的一面是怎么在无数种递归结构里找到贴合业务的那一种。我的体会是递归类型设计最核心的不是“能不能递归”而是“哪里终止”。设计阶段先找叶子节点把不包含子结构的形态列举出来再找容器节点明确它通过什么字段引入子结构是列表、映射还是单个引用。叶子确定之后递归分支才不会被设计得含糊。比如做 JSON叶子是数字字符串布尔容器是数组和对象做表达式叶子是常量变量容器是二元运算和函数调用。这个顺序我屡试不爽。另一个体会是尽量让递归分支只持有一种“递归容器”。如果既有children: List[Tree]又有parent: Option[Tree]遍历时两种引用同时存在处理不好就循环了。需要父引用的场合不要硬塞可以参考数据库设计里“只存子引父引用时再查”的思路。复杂自指涉结构不是不能存在而是每个递归边都应该能被测试覆盖否则重构时算法复杂度会直接失控。最后分享一个我自己一直在用的小技巧递归类型定义好后先只写两个函数一个是统计大小的size一个是查找子节点的find。这两个函数能通过说明类型能承载基本的遍历剩下的业务规则只是在这两根支柱上扩展而已。任何自指涉数据结构的迭代都可以从这两个函数快速起步。 Scala 递归类型与 ADT 实战：从 JSON 解析到 Scala 3 enum
1. 为什么“身体里长着自己”的类型是硬需求1.1 树、JSON、文件系统结构递归到处都是我第一次对 Scala 递归类型产生强烈兴趣是因为一个看起来非常普通的任务用 Scala 写一个 JSON 解析器。JSON 的语法结构是天然自指的一个 array 的元素还是 json一个 object 的字段值还是 json整个数据定义里反复出现自己的名字。如果类型系统不能表达“这个类型里面包含自己”那写出来的代码就只能在运行时靠各种比较粗糙的手段兜底。树结构更是如此文件系统目录、表达式语法树、组织结构、依赖关系图全是同一个模式我定义某种形态的节点节点再嵌入同样形态的节点唯一的不同只是具体业务数据的形态有差异。递归类型就是那类专门描述“自指涉数据结构”的工具。它让编译器知道这个类型里面真的可以有同类型的子节点并且这种嵌套可以无限延展下去一直到某个明确的终止条件为止。不只是工程语言数学里早就这么干了自然数可以定义为零或某个自然数的后继列表可以定义为空或“一个元素加上一个列表”。递归类型不是某个特定语言的语法糖而是对“结构嵌套”这种现实需求的直接建模。1.2 不用递归类型时项目会滑向哪里有个很典型的反面模式你多半见过业务里要保存一棵树于是有人图省事直接用Map[String, Any]来表示节点。键是字段名值是基本类型或者子节点列表。第一眼看起来灵活项目推进到一个阶段就会开始出问题。取值要一层层做asInstanceOf子节点类型稍微变一下处理代码就要改一片很多错误不是在编译时暴露的而是在线上运行时变成异常。如果数据形状更复杂一点比如节点可能分为“普通节点”“叶子节点”和“带元数据的节点”这类方案基本会退化成一大片手工类型判断。更难受的是编辑器跳转不灵重构不敢做团队新成员看半天也不知道一个节点到底能装什么。递归类型解决的不是“能不能写出来”的问题而是“类型约束能不能在编译期帮你兜住”的问题。用 ADT 表达自指涉结构所有分支都写在同一处模式匹配时编译器会提醒你哪些情况没处理改动分支时也能通过警告快速发现受影响的调用点。1.3 一门语言的类型系统本质上是在为“结构真相”背书递归类型之所以值得认真掌握是因为它把“结构上允许什么”这件事直接提升到了类型层。我一直强调一个观点类型定义就是业务设计文档而且是会被编译器执行的文档。当你写下case class Folder(name: String, children: List[Folder])时你其实是在声明一条铁律文件夹的 children 也是一个文件夹。所有递归函数无论深度遍历还是规模统计都建立在这个不动点上。反过来只要破坏这种嵌套关系比如塞一个字符串进去编译器立刻拒绝。这种能力在 Scala 3 的 enum 上体现得特别清晰。enum 的分支集合是封闭的编译器可以拿着模式匹配里的每个分支去核对定义漏了哪个就是警示。这种穷尽性检查对自指涉结构价值极大因为递归结构的遍历代码通常是一连串 match 分支稍不留神就会漏掉一个递归子结构编译器能帮你把漏分支的隐患在产生 bug 之前就标出来。2. 从 Scala 2 到 Scala 3递归类型的主要写法2.1 先备好运行环境Linux 上跑起来很简单后面所有例子都用 Scala 3 语法运行环境其实很轻。在 Linux 上最省事的是先装好 JDK 17然后用 SDKMAN 或直接下载 scala-cli。scala-cli 非常适合这种纯文件测试写一个.scala文件跑一句scala-cli run demo.scala就能看到结果。# 建议先安装 SDKMAN再装 scala-cli 和 scala 3 sdk install java 17-tem sdk install scala sdk install scalacli然后新建一个文件比如RecTypeDemo.scalamain def demo(): Unit println(recursive type demo ready)命令行执行scala-cli run RecTypeDemo.scala看到输出说明环境就绪。日常练习不需要上重型构建工具等代码多起来再引入 sbt 也不迟。这个工作流在 Linux 服务器上同样顺手没有图形界面也没关系写的 Scala 代码和你在 IDE 里看到的完全一致。2.2 Scala 2 经典流派sealed trait 加 case classScala 2 时代表达自指涉结构的主流方式是 sealed trait 加上一堆 case class 子类。jargon 里常把这组东西叫 ADTAlgebraic Data Type代数数据类型。它为什么适合递归类型因为 trait 负责定义“总体形状”而每个子类负责一种具体构造形态构造形态里可以再次引用 trait 本身。以最经典的表达式树为例sealed trait Expr object Expr: case class Num(value: Int) extends Expr case class Add(left: Expr, right: Expr) extends Expr case class Mul(left: Expr, right: Expr) extends ExprAdd的两个字段类型还是Expr所以写出了表达式的无限嵌套。sealed 关键字限定了子类只能出现在同一个文件里这让编译器可以枚举所有分支模式匹配的穷尽性检查才能生效。只要有人改了Expr的分支所有遍历代码都可能出现编译警告这比运行时才发现要踏实太多。这种写法的好处是老项目迁移成本低Scala 2.13 和 Scala 3 都能跑。缺点是样板代码稍微多一点每个子类要写extends Expr定义 Enum 语义时不如 Scala 3 直接。2.3 Scala 3 流派enum 让递归分支更直观Scala 3 引入了真正的 enum写同样一套结构代码会更紧凑也更接近“节点只有这几种形态”的直觉enum Expr: case Num(value: Int) case Add(left: Expr, right: Expr) case Mul(left: Expr, right: Expr)分支直接缩进在 enum 内部递归引用Expr不会产生任何歧义。写遍历函数时分支名称携带构造参数模式匹配非常舒展def eval(expr: Expr): Int expr match case Expr.Num(value) value case Expr.Add(left, right) eval(left) eval(right) case Expr.Mul(left, right) eval(left) * eval(right)这段函数就是递归类型的标准搭档以递归定义为基础按分支遍历结构区分终止分支和递归展开分支再把子表达式结果合并起来。Scala 3 的 enum 还支持泛型和类型参数比如enum Tree[A]可以做多态递归树功能上没有短板。2.4 为什么type Expr List[Expr]是不成立的初学者经常会碰一个坎好像只要类型别名叫自己就行。比如写了type JsonNode Map[String, JsonNode]Scala 编译器会直接拒绝因为 type alias 不是真正的新类型它只是替换符号。编译器一旦展开别名看到的就是Map[String, Map[String, Map[String, ...]]]一个永远停不下来的展开过程于是报出循环引用错误。要表达递归结构必须有一个真名实姓的类或枚举类型作为递归入口case class、enum、trait 都可以唯独纯 type alias 不行。这背后的原因很有趣递归类型需要能判定“这个值到底长什么样”而真实类型必须有一个明确的构造点。case class 有运行时构造入口enum 有确定的 case 集合type alias 没有。理解这条边界能少踩很多“为什么我写的递归类型编译不过”的坑。3. 实操用递归类型写出真正能跑的自指涉结构3.1 定义 JSON AST每一层都由六个分支接管我常用 JSON 模型来演示递归类型设计因为它足够简单又覆盖了嵌套、列表、映射、终止分支这几种核心场景。用 Scala 3 定义enum Json: case JNull case JBool(value: Boolean) case JNumber(value: BigDecimal) case JString(value: String) case JArray(items: Vector[Json]) case JObject(fields: Map[String, Json])第一眼看过去JArray里的Vector[Json]是递归JObject里的Map[String, Json]也是递归。前者是“同结构可重复”后者是“通过键名引用自身”。这种定义把 JSON 的完整结构压缩在六行里比任何文档都精确。设计递归类型时我给自己定过一条规矩每个递归分支都必须有一个清晰的集合容器不要让单个字段以Option[Json]的形式玩花活。Option[Json]当然能表示可空字段但当数据变成深层嵌套时Option 套 Option 会让代码苦不堪言。更推荐的做法是让字段默认给一个空值比如JArray直接给空VectorJObject直接给空Map然后用分支本身表达语义递归深度就不容易失控。3.2 递归遍历函数match 分支就是结构的镜子定义完类型后遍历逻辑会显得几乎是自动生成的。比如写一个prettyPrint把 JSON 缩进打印出来def pretty(json: Json, indent: Int 0): String val pad * indent json match case Json.JNull pad null case Json.JBool(b) pad b.toString case Json.JNumber(n) pad n.toString case Json.JString(s) pad \ s \ case Json.JArray(items) items.map(item pretty(item, indent 1)).mkString(pad [\n, ,\n, \n pad ]) case Json.JObject(fields) fields .map { case (k, v) pad \ k \: pretty(v, indent 2) } .mkString(pad {\n, ,\n, \n pad })模式匹配的每个分支恰好对应 enum 定义里的每个 case。这里是递归类型的另一个魅力你不用专门写一个“判断当前节点属于什么类型”的调度器模式匹配天然按类型分发。漏掉JNull编译器立刻标出 non-exhaustive warning新增一种 case所有 match 位置都会被警告逐个补上就行。3.3 文件系统目录树给递归节点配上名字和子节点再把递归类型用到更贴近系统编程的场景。文件目录是标准树目录套目录文件是叶子case class FsNode( name: String, isDirectory: Boolean, children: Vector[FsNode] Vector.empty )这个 case class 只有一个递归容器字段。它非常简洁但要注意一点当目录和文件的差异用一个布尔字段而非不同分支表达时遍历代码里不可避免要写if node.isDirectory。我并非反对这种方式只是提醒布尔字段分支会让类型模型的“分支语义”变弱不如 enum 清晰。做成完整 ADT 会更稳enum FsEntry: case Dir(name: String, children: Vector[FsEntry]) case File(name: String, sizeBytes: Long)这时递归类型跟业务语义彻底对齐只有 Dir 允许有子节点File 本身就是终止节点。随之而来的遍历函数只剩三种情况倒也能接受def totalSize(entry: FsEntry): Long entry match case FsEntry.File(name, size) size case FsEntry.Dir(name, children) children.map(totalSize).sum当递归分支和非递归分支被类型强制区分出来代码分支就不会出现“忘了处理文件节点”的尴尬。3.4 泛型递归LinkedList 与 Tree 的通用形态自指涉结构经常需要携带不同载荷这时要给递归类型加泛型参数。LinkedList 是经典enum LinkedList[A]: case Empty case Cons(head: A, tail: LinkedList[A]) def size[A](list: LinkedList[A]): Int list match case LinkedList.Empty 0 case LinkedList.Cons(h, t) 1 size(t)这里的递归点是tail: LinkedList[A]一旦给A换成具体类型整个链表的元素类型就固定下来。协变标注A是安全的因为我们只把A放在读取位置没有var head: A这类可变写入。递归类型跟泛型参数组合是常态JSON AST 里的Map[String, Json]本质上也是一种泛型递归只是容器换成 Map 而已。4. 循环引用、互递归类型和惰性求值4.1 类型递归和值递归要分清楚递归类型说的是“类型定义里包含自己”但是运行时能不能构造出循环引用是另一个层面的问题。最常见的例子是有向图节点 A 指向节点 BB 又指回 A。类型上两个节点都可以是Node。但如果按普通字段直接构造就会在初始化时遭遇“先有鸡还是先有蛋”的死结。Scala 的 lazy val 能化解这个死结。它把初始化推迟到第一次访问时让两个对象互相能看到对方同时形成循环引用。case class Node(name: String, neighbors: List[Node]) object Graph: lazy val a: Node Node(a, List(b)) lazy val b: Node Node(b, List(a))这里a定义里用了bb定义里用了a类型上两边都是Node值上靠 lazy 机制完成互相构造。这种写法适合表示不可变的循环引用结构比如状态机、依赖环、邻近关系。要注意的是打印这种结构会绕圈子不要指望toString能给出让人舒服的结果更别直接用递归函数去求“无限深图”的深度否则栈肯定爆。4.2 互递归类型两个类型互相引用对方自指涉数据结构不一定是单个类型绕回自己还可以是多个类型互相绕。编译器和类型检查器里非常常见语法树里的表达式和发展环境可以互相引用。简化一下是这样enum Expr: case Var(name: String) case Let(name: String, value: Expr, body: Expr) final case class Env(bindings: Map[String, EnvEntry]) enum EnvEntry: case Value(expr: Expr) case Scope(env: Env)Expr里出现EnvEntryEnvEntry里出现Expr。它们互为递归。Scala 允许这样的定义但要注意最好把它们放在同一个文件避免复杂包级循环。这种互递归结构如果换成接口加实现类写起来会散落很多而用 ADT 一口气列出来类型之间的引用关系一目了然。我个人体会是只要出现两个以上的互递归类型就应该把整个家族定义集中在一个文件里管理。类型本身是“结构真相”让真相集中在显眼处后续维护时打开一个文件就能看到全局。4.3 递归边界与 F-bounded 多态有些自指涉类型不是面向数据的而是面向操作约束的。比如想定义一个“可比较、且比较时只能与自身类型比较”的接口Scala 里常见写法是trait Comparable[T : Comparable[T]]: def compare(other: T): Int注意T : Comparable[T]这种递归边界让 T 必须是“实现了 Comparable[T] 的类型”。比如Person实现Comparable[Person]之后compare就只能接收Person不能拿Person和Company瞎比。这个模式叫 F-bounded 多态它是自指涉类型在类型参数上的一种递归表达。理解它对阅读泛型库源码非常有帮助。很多 Scala 类型类的设计都依赖这种“类型递归边界”Shapeless 的Generic[T]、Cats 的Show[T]虽然平常写法不直接自指但高级抽象里到处都是 T 与某个更高 kind 类型互相约束的影子。4.4 递归结构一定会遇到终止问题写递归函数时一句老话永远适用没有终止分支的递归不是数据结构是灾难。类型允许无限嵌套不意味着遍历就得无限跑而是要求遍历函数在每个分支上给出处理尤其是那个不再递归下去的终止分支。比如对Json求节点总数def count(json: Json): Int json match case Json.JNull | Json.JBool(_) | Json.JNumber(_) | Json.JString(_) 1 case Json.JArray(items) 1 items.map(count).sum case Json.JObject(fields) 1 fields.values.map(count).sum终止分支是那些不含子结构的叶子 case。漏掉任何一个叶子分支模式匹配会给出提醒漏掉递归分支可能直接导致栈溢出。判断递归函数是否健康就看每个递归调用的参数是不是都在向叶子结构收敛。这个判断应该成为条件反射。5. 实战排雷调试递归类型时踩过的坑5.1 “illegal cyclic reference”通常是类型标注缺失Scala 的类型推导虽然强大但碰到递归结构时编译器也需要更多线索。我见过不少编译报错报的是illegal cyclic reference第一反应以为递归类型写错了。其实很多时候不是类型定义错而是推导过程走进了死胡同。比如某段代码里写了一个返回自身的函数不给返回类型编译器猜不出来一个有限大小的类型签名就会拒绝。经验是递归函数务必显式标注返回类型。它不仅让代码可读也让编译器的推导路径短很多。一旦显式标注原本神秘的 cyclic reference 错误往往会变成普通类型不匹配立刻能看清是哪个字段塞错了。递归类型定义也同理宁可多写几行类型签名也绝不在模式匹配和递归调用里全靠推导。5.2 深递归导致 StackOverflow递归类型允许很深的结构但 JVM 的方法调用栈不是无限的。构造一个百万层的 JSON 数组再写递归count大概率会在某层栈溢出。这个问题不是类型系统错误而是运行时物理限制。处理方式有几种。最简单的是把递归转成尾递归并加上tailrec让编译器验证但很多递归结构天然不是尾递归比如遍历树时先处理左边再处理右边每次调完还有后续操作。这种场景可以用显式栈模拟递归def countIterative(json: Json): Int val stack scala.collection.mutable.Stack[Json](json) var total 0 while stack.nonEmpty do stack.pop() match case Json.JArray(items) items.foreach(stack.push) case Json.JObject(fields) fields.values.foreach(stack.push) case _ () total 1 total手动栈用循环替代递归深度不再受调用栈限制。自指涉结构深度比较依赖这个技巧值得熟练掌握。5.3 协变标注和不可变字段是递归类型的好朋友给递归类型加泛型参数时最常见的编译错误来自方差标注。如果写出enum Node[A] { case Cons(head: A, next: Node[A]) }可以编译但如果字段是可变的case class MutableNode[A](var next: Option[MutableNode[A]])再标记A编译器就会抗议因为var字段既是读出又是写入破坏了协变需要的“只读”约束。我踩过这种坑想让Node协变但又想保留可变 next 字段最后只能在两者之间取舍。真正适合协变的是不可变递归结构比如List[A]、Tree[A]可变结构就老老实实不标方差。这个约束不是烦人的限制它其实保证了类型安全否则一个Node[Dog]可能会在运行时被塞进Node[Animal]里。5.4 匹配警告一定要当回事Scala 编译器对 sealed trait 和 enum 的穷尽性检查非常用心。递归类型的遍历一旦漏分支通常闪一下 warning。它的语气很温和但我们不能把自己养成忽略 warning 的习惯。把漏掉的分支补上或者明确写出case _ 都是可以的选择但要刻意决定而不是放任不管。我习惯在构建配置里开启-Werror或者-Xfatal-warnings让 warning 直接变成 error。这样新增分支后所有受影响的递归遍历函数都会被编译错误点醒。第一次会觉着残酷但交付质量确实提高了没有一处递归分支能被悄悄遗忘。症状可能原因处理思路illegal cyclic reference递归函数缺返回类型或 type alias 直接自指给函数补显式类型把 alias 改成 case class / enumvariance 编译错误可变字段出现在递归泛型类型中改成不可变字段或去掉协变标注StackOverflow递归深度超过 JVM 栈容量改尾递归或改为显式栈循环non-exhaustive warning新增分支后遍历函数没更新逐个 match 补分支或统一生成默认分支启动后才报类型错误数据层用 Any 绕过类型检查改用完整 ADT尽早把结构交给编译器6. 设计递归类型的一页心得把“艺术与科学”落到实处回到标题里那个“艺术与科学”。科学的一面是类型规则明确递归边界、方差、穷尽性检查都有硬性的编译判断艺术的一面是怎么在无数种递归结构里找到贴合业务的那一种。我的体会是递归类型设计最核心的不是“能不能递归”而是“哪里终止”。设计阶段先找叶子节点把不包含子结构的形态列举出来再找容器节点明确它通过什么字段引入子结构是列表、映射还是单个引用。叶子确定之后递归分支才不会被设计得含糊。比如做 JSON叶子是数字字符串布尔容器是数组和对象做表达式叶子是常量变量容器是二元运算和函数调用。这个顺序我屡试不爽。另一个体会是尽量让递归分支只持有一种“递归容器”。如果既有children: List[Tree]又有parent: Option[Tree]遍历时两种引用同时存在处理不好就循环了。需要父引用的场合不要硬塞可以参考数据库设计里“只存子引父引用时再查”的思路。复杂自指涉结构不是不能存在而是每个递归边都应该能被测试覆盖否则重构时算法复杂度会直接失控。最后分享一个我自己一直在用的小技巧递归类型定义好后先只写两个函数一个是统计大小的size一个是查找子节点的find。这两个函数能通过说明类型能承载基本的遍历剩下的业务规则只是在这两根支柱上扩展而已。任何自指涉数据结构的迭代都可以从这两个函数快速起步。