示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载本篇指南聚焦《Functional Programming in Scala》(fpinscala) 仓库中第五章laziness练习 10 的官方提示文档 answerkey/laziness/10.hint.md逐字拆解该提示的意图并对照仓库内的参考答案、练习骨架与单元测试讲透如何用第 2 章学过的函数式循环技巧构造一个无限延展的斐波那契 LazyList。读完你将掌握惰性流LazyList递归构造的本质、递归辅助函数go在无限数据结构中的应用以及同一问题在unfold视角下的另一种写法。一、题目背景第 5 章练习 10 到底要做什么在 fpinscala 仓库中第五章对应的练习文件是 src/main/scala/fpinscala/exercises/laziness/LazyList.scala。其中定义了一个自定义的惰性列表类型enum LazyList[A]: case Empty case Cons(h: () A, t: () LazyList[A])与普通List的关键区别在于Cons的头部h和尾部t都是按名调用by-name的函数也就是说一个元素在被真正访问之前并不会被求值。这正是无限数据结构得以成立的前提——我们可以在不实际生成全部元素的情况下构造一个理论上无限长的序列。练习 10 的题目落在该文件的 object 部分骨架如下lazy val fibs: LazyList[Int] ???即用惰性流表示斐波那契数列0, 1, 1, 2, 3, 5, 8, 13, …每个元素只在前一个元素被访问时才计算出来。官方提示 answerkey/laziness/10.hint.md 的全文只有一句话Chapter two discussed writing loops functionally, using a recursive helper function - how would that apply here? 第 2 章讨论过如何用函数式的方式写循环——借助递归辅助函数——这一技巧在这里该如何应用这句话虽然短却精准地指向了答案的核心形态不要试图一次性算出整个数列而是用一个带参数的递归辅助函数逐步吐出下一个元素。二、提示背后的知识铺垫第 2 章的函数式循环要理解这条提示先回到第 2 章的练习骨架 src/main/scala/fpinscala/exercises/gettingstarted/GettingStarted.scala。该文件里给出了函数式循环的经典范例——阶乘def factorial(n: Int): Int annotation.tailrec def go(n: Int, acc: Int): Int if n 0 then acc else go(n-1, n*acc) go(n, 1)这里的关键模式是外部函数定义一个局部递归辅助函数go由go携带累积状态参数完成迭代最后以初始状态调用go。整个过程没有var、没有while纯粹靠递归传递状态这就是用函数式方式写循环的标准姿势。第 2 章练习 1求第 n 个斐波那契数的答案 answerkey/gettingstarted/01.answer.md 也采用了同一手法def fib(n: Int): Int annotation.tailrec def loop(n: Int, prev: Int, cur: Int): Int if n 0 then prev else loop(n - 1, cur, prev cur) loop(n, 0, 1)注意loop的两个状态参数prev、cur正是当前数与下一个数——这个状态设计思路稍后会原封不动地迁移到 LazyList 版本中。第 2 章练习 2 的答案 answerkey/gettingstarted/02.answer.mdisSorted同样依赖go(n: Int)式的递归辅助函数。回到提示本身how would that apply here?——答案是把第 2 章用递归辅助函数携带状态的思路应用到无限流上只是把返回单个值换成返回一个 Cons 单元格其尾部继续递归。三、标准答案逐行拆解仓库给出的官方答案是 answerkey/laziness/10.answer.mdval fibs def go(current: Int, next: Int): LazyList[Int] cons(current, go(next, current next)) go(0, 1)完整的可运行版本位于答案模块 src/main/scala/fpinscala/answers/laziness/LazyList.scala第 202–205 行val fibs def go(current: Int, next: Int): LazyList[Int] cons(current, go(next, current next)) go(0, 1)我们逐行理解第 1 步局部递归辅助函数go(current, next)。它携带两个 Int 状态current是当前要输出的斐波那契数next是下一个斐波那契数。这和上一节第 2 章fib答案里loop(prev, cur)的状态设计一脉相承——这就是提示所说的第 2 章技巧在这里的应用。第 2 步cons(current, go(next, current next))。cons是 object 中定义的聪明构造器src/main/scala/fpinscala/answers/laziness/LazyList.scala 第 180–183 行它把按名参数缓存进lazy val保证每个元素最多只被求值一次def consA: LazyList[A] lazy val head hd lazy val tail tl Cons(() head, () tail)头部current立即成为流中的元素尾部go(next, current next)则是按名传递的只有当你访问流的第二个元素时它才会被真正求值。于是计算下一个数的动作被推迟到需要时——这正是惰性流无限延展的核心机制go的每一次递归调用都只承诺生成一个元素而不是一口气算完。第 3 步go(0, 1)作为初始状态。斐波那契数列以 0、1 开头因此用(current 0, next 1)启动整个生成过程。展开求值序列观察状态如何滚动访问次数当前输出 current下次携带的 next实际输出的流1010, 1, 1, 2, …2111, 1, 2, 3, …3121, 2, 3, 5, …4232, 3, 5, 8, …每个go(current, next)都输出current并生成下一个状态(next, current next)——恰好对应斐波那契递推公式F(n) F(n-1) F(n-2)。流的取值序列就是 0, 1, 1, 2, 3, 5, 8, …。四、与同章其他无限流构造的横向对比fibs不是本章唯一的无限流。同一练习文件的 object 中还定义了其他几个通过对比可以更清楚地看出go递归模式的普适性ones练习 5.8 相关——最简单的自引用无限流val ones: LazyList[Int] LazyList.cons(1, ones)它不需要状态参数因为每个元素都是常数 1。from(n)练习 5.9答案见 answerkey/laziness/09.answer.md——从 n 开始递增的无限整数流def from(n: Int): LazyList[Int] cons(n, from(n 1))它只携带一个状态n每次递归n 1。提示 09answerkey/laziness/09.hint.md同样在引导读者使用递归参考ones的递归写法from该如何递归定义fibs练习 5.10——需要两个状态参数因为斐波那契的递推依赖前两个数。这正是go(current, next)存在的原因把前两个数打包成一对状态让递推关系在状态转移中自然表达。无限流状态数量状态转移输出ones0无1, 1, 1, …from(n)1n → n1n, n1, n2, …fibs2(c, n) → (n, cn)0, 1, 1, 2, 3, …共同点三者都依靠cons的按名尾部实现边访问边生成从而在常数级内存开销下表示无限序列区别只在于状态的数量与转移规则。掌握go递归辅助函数后你可以用同一模板构造任意状态递推型无限流。五、测试如何验证fibs的正确性仓库为本章练习配备了基于属性测试的单元测试套件 src/test/scala/fpinscala/exercises/laziness/LazyListSuite.scala其中与fibs直接相关的测试为test(LazyList.fib)(genLengthOfFibonacciSeq): n assertEquals(fibs.take(n).toList, theFirst21FibonacciNumbers.take(n).toList)theFirst21FibonacciNumbers定义于 src/test/scala/fpinscala/exercises/common/Common.scalalazy val theFirst21FibonacciNumbers IndexedSeq(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765)genLengthOfFibonacciSeq从 0 到 21 之间随机选择截取长度断言逻辑是取fibs前 n 个元素转成普通 List 后与已知的前 21 个斐波那契数的前 n 个完全相等。这个测试同时验证了三件事fibs的前缀正确、take与toList在惰性流上工作正常、以及无限流可以被安全地按需截取。注意fibs在练习骨架里是lazy val fibs: LazyList[Int] ???src/main/scala/fpinscala/exercises/laziness/LazyList.scala 第 56 行lazy val保证整个无限流只会被初始化一次多个消费者共享同一份惰性求值的元素缓存。运行该测试的方式依据 README.mdscala-cli test . -- fpinscala.exercises.laziness.*注意fibs在练习文件中尚未实现为???因此该测试只有在完成练习后才会通过——这正是仓库边做题边验证的学习闭环。六、进阶视角用unfold重新表达同一个递推练习 5.11 引入了更通用的核心原语unfold提示见 answerkey/laziness/11.hint.md答案见 answerkey/laziness/11.answer.mddef unfoldA, S(f: S Option[(A, S)]): LazyList[A] f(state) match case Some((h,s)) cons(h, unfold(s)(f)) case None emptyunfold的语义是给定一个状态S用函数f把它映射为Option[(A, S)]——Some表示产出元素 A 并转移到新状态None表示流终止。你会发现练习 5.10 中go的手写递归本质上就是unfold的一个特例状态是(current, next)产出是current新状态是(next, current next)永不返回None所以流是无限的。因此练习 5.12答案见 answerkey/laziness/12.answer.md给出了fibs的unfold版本val fibsViaUnfold: LazyList[Int] unfold((0,1)): case (current, next) Some((current, (next, current next)))两种写法的对照fibs练习 5.10 答案fibsViaUnfold练习 5.12 答案核心结构局部递归辅助函数go高阶函数unfold状态(current, next)(current, next)状态转移go(next, current next)(next, current next)终止条件无天然无限从不返回None从实现机制看unfold内部正是用cons(h, unfold(s)(f))递归展开的与go的递归如出一辙区别在于unfold把递归骨架抽象成了通用工具让调用方只需描述单步状态转移。理解 5.10 的手写递归是真正读懂unfold的最佳铺垫——这也解释了为什么练习 5.11 的提示要求读者复习 4.1 中操作Option的技巧answerkey/laziness/11.hint.md。配套测试LazyList.fibsViaUnfoldsrc/test/scala/fpinscala/exercises/laziness/LazyListSuite.scala对两种实现施加完全相同的断言进一步印证二者等价test(LazyList.fibsViaUnfold)(genLengthOfFibonacciSeq): n assertEquals(fibsViaUnfold.take(n).toList, theFirst21FibonacciNumbers.take(n).toList)七、小结一条提示如何串起整章知识回到 answerkey/laziness/10.hint.md 那句只有一行的提示——它其实浓缩了三个层次的知识迁移回望第 2 章函数式循环 递归辅助函数携带状态参见 GettingStarted.scala 的factorial与 gettingstarted/01.answer.md 的fib应用于第 5 章把返回单个值的go升级为返回 Cons 单元格的go配合cons的按名尾部就得到无限流通向下一题手写递归的状态转移模式正是练习 5.11/5.12 中unfold抽象的直接原型。如果你正在做这道练习建议按如下顺序自查先独立写出go(current, next)版本用fibs.take(10).toList在 REPL 里验证输出是否为List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)再运行scala-cli test . -- fpinscala.exercises.laziness.LazyListSuite.LazyList.fib通过官方属性测试最后尝试用unfold重写并对照fibsViaUnfold。完成这三步你就同时掌握了递归辅助函数与核心原语抽象两套构造无限数据结构的核心武器。赞分享示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载相关推荐fpinscala 惰性求值实战用递归辅助函数构造无限斐波那契 LazyListChapter 5 练习 10 解答深度解析fpinscala 惰性求值实战用递归辅助函数构造无限斐波那契 LazyListChapter 5 练习 10 解答深度解析 本文围绕《Functiona示例工程fpinscala 练习精解用 Scala 3 尾递归实现斐波那契数列第 2 章 Exercise 1fpinscala 练习精解用 Scala 3 尾递归实现斐波那契数列第 2 章 Exercise 1 导读 本文围绕 fpinscala 仓库第 2 章示例工程fpinscala 实战用尾递归函数实现斐波那契数列——gettingstarted 第 1 题01.hint.md完整解读fpinscala 实战用尾递归函数实现斐波那契数列——gettingstarted 第 1 题01.hint.md完整解读 导读 本文围绕 fpinsc示例工程上一篇终极四足机器人控制平台walk-these-ways如何从零开始训练动态行走AI模型下一篇Swift开发者必备RxAnimated自定义动画的完整实现指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考