示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载本文以 fpinscala 仓库《Functional Programming in Scala》配套练习中第 3 章datastructures习题 27 的标准答案为骨架深入剖析二叉树上depth方法的实现原理如何利用 Scala 3 的enum与模式匹配递归求出树的最大深度。文章结合仓库中的习题占位符、完整答案源码与属性测试用例讲解叶子基例、分支递推式、与size/maximum的结构同构性、复杂度边界并延伸到用fold统一抽象习题 29读完后你能独立写出一份可编译、可被测试验证的Tree.depth实现并理解其背后的递归思维模式。一、背景fpinscala 的 Tree 代数数据类型在 fpinscala 的第 3 章datastructures中作者用 Scala 3 的enum定义了一棵不可变的二叉树enum Tree[A]: case Leaf(value: A) case Branch(left: Tree[A], right: Tree[A])Leaf(value: A)表示叶子节点携带一个类型为A的值Branch(left: Tree[A], right: Tree[A])表示内部节点由左右两棵子树构成A表示协变类型参数即Tree[Dog]可以被当作Tree[Animal]使用。该定义位于仓库的 习题占位符 Tree.scala。这一章的全部练习围绕这棵树的递归遍历展开要求读者用纯函数式的方式实现size、depth、map、fold等操作而习题 27 的任务正是实现depth树的深度对应占位符def depth: Int ???该占位符在 习题源码 中而官方完整答案位于 答案源码 Tree.scala。二、习题 27 的官方答案与核心思路习题 27 答案 给出的实现非常简洁/* Again, note how similar the implementation is to size and maximum. */ def depth: Int this match case Leaf(_) 0 case Branch(l, r) 1 (l.depth.max(r.depth))答案注释开门见山地提醒读者这个实现的形态与size、maximum惊人地相似。这是第 3 章刻意设计的伏笔——三者在结构上都是「对树做递归折叠」区别只在于叶子返回什么分支处如何组合左右子树的递归结果。这正是后续习题 29 引入fold来统一抽象这些递归模式的动机。三、逐行拆解模式匹配下的递归定义depth的定义遵循代数数据类型ADT的经典套路为每一种构造子constructor写一个分支。基例叶子case Leaf(_) 0单节点的树只有一片叶子深度为0。这里_表示我们不关心叶子携带的具体值——深度与值无关只与树的形状有关。递推分支case Branch(l, r) 1 (l.depth.max(r.depth))一个分支节点的深度等于「左右子树中较深的那棵的深度再加 1」。其中l.depth/r.depth对左右子树递归调用depth.max利用Int上现成的max方法取两者较大值比手写if表达式更简洁这与习题 26 中maximum的做法一致见 习题 26 答案外加的1表示当前这个Branch节点本身贡献的一层。语义澄清这里的「深度」度量什么按照这个定义depth实际度量的是从根到最远叶子所经过的Branch边数而不是节点总数单叶子Leaf(1)→0Branch(Leaf(1), Leaf(2))→1 max(0, 0) 1三层满二叉树 →2。也就是说「边数制深度」的基例是0。如果某个应用需要「节点数制深度」单节点为 1只需把基例改为1即可递推式保持不变——这是读者在实际工程中需要自行约定的细节。手工推演一个例子考虑树Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))Branch / \ Leaf(1) Branch / \ Leaf(2) Leaf(3)递归求值过程depth(Branch(...)) 1 max(depth(Leaf(1)), depth(Branch(Leaf(2), Leaf(3))))depth(Leaf(1)) 0depth(Branch(Leaf(2), Leaf(3))) 1 max(depth(Leaf(2)), depth(Leaf(3))) 1 max(0, 0) 1回代depth 1 max(0, 1) 2整棵树深度为2与直觉一致最长的根到叶子路径经过了两个Branch。四、与 size、maximum 的结构同构一次「模板式」递归答案注释强调depth与size、maximum的相似性值得展开对比。仓库中三个练习的标准实现分别位于习题 25size答案 与 答案源码def size: Int this match case Leaf(_) 1 case Branch(l, r) 1 l.size r.size习题 26maximum答案 与 答案源码extension (t: Tree[Int]) def maximum: Int t match case Leaf(n) n case Branch(l, r) l.maximum.max(r.maximum)习题 27depth答案。把三者并排模板结构一目了然操作叶子分支返回分支节点组合方式语义size11 l.size r.size两子树之和再加 1统计全部节点数maximumn叶子值l.maximum.max(r.maximum)取两子树较大值求全树最大值depth01 l.depth.max(r.depth)取较深子树再加 1求最长根叶路径的边数三个函数都遵循同一个骨架匹配叶子 → 返回某个「基值」 匹配分支 → 用某个二元组合函数处理两个子树的递归结果。区别只在于基值与组合函数的不同。识别出这种「模板」是函数式编程的核心能力——它正是习题 29fold所抽象的对象。换句话说depth不是孤立的技巧而是「把递归结构参数化」这一思想的实例之一。五、复杂度与栈使用边界时间复杂度每个节点恰好被访问一次递推式T(n) T(left) T(right) O(1)因此整体复杂度为O(n)其中 n 为树中节点总数。空间复杂度调用栈该实现不是尾递归Branch分支必须先递归完成左右子树才能执行max与加法无法直接改写为tailrec累积器风格。因此运行时调用栈深度与树的深度成正比约等于树高。对于平衡树栈深约为 O(log n)完全没有压力对于退化树如全部向左倾斜、形似链表树高趋近 n递归栈深也趋近 O(n)可能出现StackOverflowError。fpinscala 第 3 章在讲解List上的map时已讨论过类似的栈使用问题可参考 List 习题源码 中的相关讨论这一警示对Tree同样适用是否关心栈深取决于你的树形态与应用场景。在大多数教学与中小规模数据场景下这份直白的递归实现是正确且可读的首选。六、仓库内的属性测试如何验证 depth 的正确性fpinscala 仓库为习题 27 提供了基于属性测试property-based testing的验证用例位于 TreeSuite.scalatest(Tree.depth)(genIntTree): tree tree match case Leaf(_) assertEquals(tree.depth, 0) case Branch(l, r) assertEquals(tree.depth, 1 l.depth.max(r.depth)) assertEquals(tree.size, toScalaList(tree).length)该测试的核心逻辑与标准答案逐字同构对任意随机生成的树断言叶子深度为 0、分支深度等于1 max(左右子树深度)。换言之测试本身就是在复述depth的规范specification用它来检验实现是否满足递归定义。测试用的树由随机生成器genIntTree构造同一文件的 TreeSuite 伴生对象val genIntTree: Gen[Tree[Int]] genTree(Gen.int) private def genTreeA: Gen[Tree[A]] def loop(): Gen[Tree[A]] Gen.boolean.flatMap: if _ then g.map(n Leaf(n)) else for left - loop() right - loop() yield Branch(left, right) loop()它以等概率随机决定当前节点是Leaf还是Branch从而覆盖从单叶子到多层的各种树形避免只测少数手工样例。若读者用scala-cli安装了构建环境可单独运行该测试scala-cli test . -- fpinscala.exercises.datastructures.TreeSuite.Tree.depth七、抽象升级用 fold 统一表达 depth习题 29 的伏笔习题 29 引入的fold是理解depth本质的最后一环。习题 29 答案 与 答案源码 给出def foldB B): B this match case Leaf(a) f(a) case Branch(l, r) g(l.fold(f, g), r.fold(f, g)) def depthViaFold: Int fold(a 0, (d1,d2) 1 (d1 max d2))fold接收两个「处理器」f: A B处理叶子把叶子值映射为结果g: (B, B) B处理分支把左右子树的折叠结果组合起来。于是depthViaFold只需指定叶子处理器a 0忽略叶子值返回基值 0分支组合器(d1, d2) 1 (d1 max d2)取较深者加 1。可以看到它和习题 27 的手写版本case Leaf(_) 0; case Branch(l, r) 1 (l.depth.max(r.depth))在语义上完全等价——手写版就是fold在「基值 0、组合函数 (x, y) 1 (x max y)」这一特定实例下的展开。这正是第四节「结构同构」观察的正式化size、maximum、depth乃至map都可以套进同一个fold模板只是传入不同的f与g。八、本地编译与运行方式fpinscala 当前仓库使用 Scala 3.3.4 与 scala-cli 构建见 build.scala 的// using scala 3.3.4指令测试框架为 munit。按照 README.md 的说明编译全部练习与答案scala-cli compile .启动 REPL 并直接试验depthscala-cli console . scala import fpinscala.answers.datastructures.Tree.* scala Branch(Leaf(1), Branch(Leaf(2), Leaf(3))).depth运行整个 datastructures 章节的测试包含Tree.depth用例scala-cli test . -- fpinscala.exercises.datastructures.*注意README 指出未完成的习题会以???占位因此全量跑测试时未作答的用例会失败随着习题逐步实现测试会陆续通过——这也正是把 习题占位符 Tree.scala 中的depth替换为本文实现后即可通过Tree.depth测试的原因。结语习题 27 虽然只有短短三行却是理解函数式递归处理代数数据类型的绝佳样本它示范了「为每个构造子写分支」的标准做法暴露了与size、maximum共享的递归模板并为fold的抽象埋下伏笔。掌握它等于掌握了Tree上一切形状相关运算的通用推导路径——先确定基值再确定组合函数剩下的交给模式匹配与递归。赞分享示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载相关推荐I-SOLAR-10.7B模型性能测试NPU vs CPU推理速度终极对比分析I SOLAR 10.7B模型性能测试NPU vs CPU推理速度终极对比分析 在人工智能模型部署领域选择合适的硬件平台对推理性能至关重要。今天我们将深入分algorithm-pattern数据结构篇二叉树与链表模板精讲algorithm pattern数据结构篇二叉树与链表模板精讲 本文详细解析了二叉树遍历模板前序、中序、后序的递归和非递归实现、DFS深度搜索与BFS层教程30 seconds of codeJavaScript 二叉树数据结构实现与遍历详解30 seconds of codeJavaScript 二叉树数据结构实现与遍历详解 导读 二叉树Binary Tree是计算机科学中最基础也最常用的层教程文档上一篇WarcraftHelper终极指南魔兽争霸III现代化增强插件完整教程下一篇WarcraftHelper重塑经典魔兽争霸3的现代化游戏体验创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考