示例工程【免费下载链接】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第 12 章 applicative 练习 17 的提示与标准答案展开核心解决一个看似矛盾的问题Traverse[F]作为Foldable[F]的子类型如何用「遍历 累积」的通用原语mapAccum优雅地实现foldLeft。读完本文你将掌握foldLeft与toList在实现思路上的同构关系理解State应用函子如何支撑mapAccum的底层机制并能把这个技巧迁移到zipWithIndex、reverse、zip等衍生操作上。一、练习背景Traverse 为什么必须自己实现 foldLeft在 fpinscala 中Traverse[F[_]]同时继承了Functor[F]与Foldable[F]两个能力trait Traverse[F[_]] extends Functor[F], Foldable[F]: self extension A def traverse[G[_]: Applicative, B](f: A G[B]): G[F[B]] fa.map(f).sequence ...这段代码来自 Traverse.scalaanswers 版。由于Foldable接口要求实现foldLeft、foldRight、foldMap等方法任何一个具体的Traverse实例如listTraverse、optionTraverse、treeTraverse都必须补齐这些折叠操作否则无法编译通过。练习 17 的 hint 文件17.hint.md给出了关键提示This implementation is very similar totoListexcept instead of accumulating into a list, we are accumulating into aBusing theffunction.也就是说foldLeft的实现思路与toList几乎完全一致——toList把元素累积进一个List[A]而foldLeft只是把「累积目标」换成任意类型B并用函数f: (B, A) B完成每一步的合并。二、答案代码逐行拆解练习 17 的标准答案17.answer.md如下extension A override def foldLeftB(f: (B, A) B): B fa.mapAccum(acc)((a, b) ((), f(b, a)))(1)逐行解释extension A为任意F[A]增加扩展方法。这里的F是外层trait Traverse[F[_]]的类型参数因此该方法对List、Option、Tree、Map等任何实现了Traverse的容器都生效。override def foldLeftB(f: (B, A) B): B覆盖Foldable中的抽象方法foldLeft。签名与标准库一致初始累积值acc在前合并函数(B, A) B在后。fa.mapAccum(acc)((a, b) ((), f(b, a)))(1)这是核心一行。mapAccum的原型来自 answers 版 Traverse.scala 第 55-62 行为def mapAccumS, B(f: (A, S) (B, S)): (F[B], S) fa.traverse(a for s1 - State.get[S] (b, s2) f(a, s1) _ - State.set(s2) yield b ).run(s)首参acc作为初始状态S B累积函数(a, b) ((), f(b, a))接收当前元素a和当前累积值b返回((), 新累积值)即只更新状态、不产出结构结尾的(1)是 Scala 3 的匿名参数占位符语法相当于mapAccum(...)._1即只取返回元组的第一项F[B]——注意这里返回的并不是结构本身而是State运行结束后取出的最终状态。与 toList 的对照同一文件中的toList实现第 36-37 行几乎同构override def toList: List[A] fa.mapAccum(List[A]())((a, s) ((), a :: s))(1).reverse对比维度toListfoldLeft初始累积值List[A]()调用方传入的acc累积函数(a, s) ((), a :: s)(a, b) ((), f(b, a))累积方向头部入栈需 reverse按f(b, a)从左到右合并结果含义元素的有序列表折叠后的单一值B这就是 hint 所说的「非常相似」二者共用同一个mapAccum引擎区别仅在于「累积到列表」还是「累积到任意B」。三、为什么 foldLeft 的累积函数参数顺序是(a, b)容易困惑的一点是mapAccum的累积函数签名是(A, S) (B, S)即元素在前、状态在后而foldLeft的合并函数签名是(B, A) B即状态在前、元素在后。答案通过两层翻转解决在传入mapAccum的 lambda 中把(a, b)解包再以f(b, a)调用真正的折叠函数实现参数顺序的交换mapAccum内部用State单子把「当前状态」串起来每次遍历一个元素时State.get取出上一步累积值调用f(b, a)得到新值再用State.set写回供下一个元素读取。这样foldLeft的语义从左到右、携带累积值就被精确地映射到了mapAccum的「状态传递」机制上。整个过程与手写foldLeft的递归等价初始值acc是状态起点f的返回值是每步之后的新状态。四、底层原理mapAccum 借助 State 应用函子实现mapAccum之所以能用一行实现关键在于State满足Applicative约束。在 State.scala 中State[S, A]定义为S (A, S)并提供get、set、modify等原语而 Applicative.scala 中提供了stateMonadMonad[State[S, _]]而Monad继承Applicativegiven stateMonad[S]: Monad[State[S, _]] with def unitA: State[S, A] State(s (a, s)) extension A override def flatMapB: State[S, B] State.flatMap(st)(f)于是traverse可以把每个元素映射成一个「读状态→算新值→写状态」的State动作再用 for-comprehensionflatMap/map串联起来最后.run(s)以初始状态执行并取出(结果, 最终状态)二元组。mapAccum与直接调用foldLeft的时间复杂度同为 O(n)但抽象层次更高——它把「遍历结构」与「累积策略」解耦这正是Traverse比单纯Foldable表达力更强的原因详见练习 15 的讨论Foldable无法构造新结构而Traverse通过保留结构可以扩展出Functor见 15.answer.md。五、练习 17 在 Traverse 方法族中的位置foldLeft不是孤立的一题它与练习 16reverse16.answer.md、练习 18fuse18.answer.md等共同构成mapAccum派生方法族def zipWithIndex: F[(A, Int)] // mapAccum 以 Int 为状态 fa.mapAccum(0)((a, s) ((a, s), s 1))(0) def reverse: F[A] // mapAccum 以 List 为状态 fa.mapAccum(fa.toList.reverse)((_, as) (as.head, as.tail))(0) def zipB: F[(A, B)] // mapAccum 消费另一结构的列表 fa.mapAccum(fb.toList): case (a, Nil) sys.error(zip: Incompatible shapes.) case (a, b :: bs) ((a, b), bs) ._1以上均出自 answers 版 Traverse.scala。可以看出mapAccum是练习 14 引入的「通用累积引擎」后续多个练习都在它之上各取所需zipWithIndex用整数计数、reverse用列表弹栈、zip用列表配对。练习 17 的foldLeft则把累积目标泛化到任意类型B是这条方法链中抽象程度最高的一环。六、验证与测试套件的对照仓库中虽未为 applicative 章节单独建测试文件但foldLeft的语义约定在 monoids 章节的测试中得到过严格验证。FoldableSuite.scala 对List、IndexedSeq、LazyList、Tree、Option五类结构分别断言foldLeft、foldRight、foldMap与标准实现结果一致例如assertEquals(list.foldLeft(0)((acc, s) s.length acc), expected)这为理解练习 17 提供了两个实用视角语义基准foldLeft必须满足「从初始值acc出发按从左到右的顺序逐个应用f」的既定语义练习 17 的mapAccum实现与这些被测试验证过的行为完全一致一致性保障由于Traverse的foldLeft是Foldable抽象方法的覆盖实现任何Traverse实例List、Option、Tree、Map[K, _]见 answers 版 Traverse.scala都能自动获得行为正确的折叠能力无需为每个容器单独编写foldLeft。七、动手验证与延伸思考想在本仓库中亲自验证这个实现可以按 README.md 的说明操作# 编译全部练习题与答案 $ scala-cli compile . # 进入 REPL 交互验证 $ scala-cli console . scala import fpinscala.answers.applicative.Traverse.* scala import fpinscala.answers.applicative.Traverse.given scala List(1, 2, 3).foldLeft(0)(_ _) // 期望 6 scala List(a, b, c).foldLeft()(_ _) // 期望 abc需要注意练习 17 的foldLeft定义在trait Traverse的扩展方法中必须在作用域内引入对应的given实例如listTraverse才能对具体类型调用。延伸思考能否用foldRight类似地实现foldLeft可以但需要借助端函数幺半群endoMonoid等技巧Monoid.scala 展示了Foldable默认实现的做法对比两种路线能更清楚mapAccum的优势。mapAccum是否比手写递归更高效二者都是线性复杂度mapAccum的价值在于复用性与可组合性——zip、reverse、foldLeft共享同一引擎减少了每个操作的重复逻辑。为什么mapAccum返回(F[B], S)而foldLeft只取状态因为foldLeft不关心重建结构B部分恒为()只关心累积的最终状态这正是「累积」与「结构变换」两个维度的分离也是Traverse设计中的关键洞察。结语练习 17 虽然只有短短一行实现却浓缩了 fpinscala 第 12 章的核心思想用State应用函子把「遍历」与「累积」统一到mapAccum这一个原语上让Traverse优雅地继承Foldable的全部折叠能力。理解foldLeft与toList的对称实现是掌握zipWithIndex、reverse、zip、fuse等一系列衍生操作的最佳起点也为后续练习 20 的composeM借助Traverse[H]实现 Monad 组合见 20.answer.md打下了基础。赞分享示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载相关推荐fpinscala 练习 16 精解用 mapAccum 与 List 栈实现 Traverse 的 reversefpinscala 练习 16 精解用 mapAccum 与 List 栈实现 Traverse 的 reverse 导读 本文围绕《Functional P示例工程用 mapAccum 实现 foldLeftfpinscala Traverse 练习 17 的答案精讲用 mapAccum 实现 foldLeftfpinscala Traverse 练习 17 的答案精讲 导读 本文讲解《Functional Program示例工程fpinscala 第 12 章练习 16 精解借助 List 栈与 mapAccum 为任意 Traverse 实现 reversefpinscala 第 12 章练习 16 精解借助 List 栈与 mapAccum 为任意 Traverse 实现 reverse 导读 本文围绕 fpi示例工程上一篇yomiyasu 推敲实战REST 与 GraphQL 技术选型文档正式文体的改写对照与语料验证下一篇PCRE 正規表達式完整入門指南從超字元到實戰解析 Apache 存取日誌zh-tw 版创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
示例工程【免费下载链接】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第 12 章 applicative 练习 17 的提示与标准答案展开核心解决一个看似矛盾的问题Traverse[F]作为Foldable[F]的子类型如何用「遍历 累积」的通用原语mapAccum优雅地实现foldLeft。读完本文你将掌握foldLeft与toList在实现思路上的同构关系理解State应用函子如何支撑mapAccum的底层机制并能把这个技巧迁移到zipWithIndex、reverse、zip等衍生操作上。一、练习背景Traverse 为什么必须自己实现 foldLeft在 fpinscala 中Traverse[F[_]]同时继承了Functor[F]与Foldable[F]两个能力trait Traverse[F[_]] extends Functor[F], Foldable[F]: self extension A def traverse[G[_]: Applicative, B](f: A G[B]): G[F[B]] fa.map(f).sequence ...这段代码来自 Traverse.scalaanswers 版。由于Foldable接口要求实现foldLeft、foldRight、foldMap等方法任何一个具体的Traverse实例如listTraverse、optionTraverse、treeTraverse都必须补齐这些折叠操作否则无法编译通过。练习 17 的 hint 文件17.hint.md给出了关键提示This implementation is very similar totoListexcept instead of accumulating into a list, we are accumulating into aBusing theffunction.也就是说foldLeft的实现思路与toList几乎完全一致——toList把元素累积进一个List[A]而foldLeft只是把「累积目标」换成任意类型B并用函数f: (B, A) B完成每一步的合并。二、答案代码逐行拆解练习 17 的标准答案17.answer.md如下extension A override def foldLeftB(f: (B, A) B): B fa.mapAccum(acc)((a, b) ((), f(b, a)))(1)逐行解释extension A为任意F[A]增加扩展方法。这里的F是外层trait Traverse[F[_]]的类型参数因此该方法对List、Option、Tree、Map等任何实现了Traverse的容器都生效。override def foldLeftB(f: (B, A) B): B覆盖Foldable中的抽象方法foldLeft。签名与标准库一致初始累积值acc在前合并函数(B, A) B在后。fa.mapAccum(acc)((a, b) ((), f(b, a)))(1)这是核心一行。mapAccum的原型来自 answers 版 Traverse.scala 第 55-62 行为def mapAccumS, B(f: (A, S) (B, S)): (F[B], S) fa.traverse(a for s1 - State.get[S] (b, s2) f(a, s1) _ - State.set(s2) yield b ).run(s)首参acc作为初始状态S B累积函数(a, b) ((), f(b, a))接收当前元素a和当前累积值b返回((), 新累积值)即只更新状态、不产出结构结尾的(1)是 Scala 3 的匿名参数占位符语法相当于mapAccum(...)._1即只取返回元组的第一项F[B]——注意这里返回的并不是结构本身而是State运行结束后取出的最终状态。与 toList 的对照同一文件中的toList实现第 36-37 行几乎同构override def toList: List[A] fa.mapAccum(List[A]())((a, s) ((), a :: s))(1).reverse对比维度toListfoldLeft初始累积值List[A]()调用方传入的acc累积函数(a, s) ((), a :: s)(a, b) ((), f(b, a))累积方向头部入栈需 reverse按f(b, a)从左到右合并结果含义元素的有序列表折叠后的单一值B这就是 hint 所说的「非常相似」二者共用同一个mapAccum引擎区别仅在于「累积到列表」还是「累积到任意B」。三、为什么 foldLeft 的累积函数参数顺序是(a, b)容易困惑的一点是mapAccum的累积函数签名是(A, S) (B, S)即元素在前、状态在后而foldLeft的合并函数签名是(B, A) B即状态在前、元素在后。答案通过两层翻转解决在传入mapAccum的 lambda 中把(a, b)解包再以f(b, a)调用真正的折叠函数实现参数顺序的交换mapAccum内部用State单子把「当前状态」串起来每次遍历一个元素时State.get取出上一步累积值调用f(b, a)得到新值再用State.set写回供下一个元素读取。这样foldLeft的语义从左到右、携带累积值就被精确地映射到了mapAccum的「状态传递」机制上。整个过程与手写foldLeft的递归等价初始值acc是状态起点f的返回值是每步之后的新状态。四、底层原理mapAccum 借助 State 应用函子实现mapAccum之所以能用一行实现关键在于State满足Applicative约束。在 State.scala 中State[S, A]定义为S (A, S)并提供get、set、modify等原语而 Applicative.scala 中提供了stateMonadMonad[State[S, _]]而Monad继承Applicativegiven stateMonad[S]: Monad[State[S, _]] with def unitA: State[S, A] State(s (a, s)) extension A override def flatMapB: State[S, B] State.flatMap(st)(f)于是traverse可以把每个元素映射成一个「读状态→算新值→写状态」的State动作再用 for-comprehensionflatMap/map串联起来最后.run(s)以初始状态执行并取出(结果, 最终状态)二元组。mapAccum与直接调用foldLeft的时间复杂度同为 O(n)但抽象层次更高——它把「遍历结构」与「累积策略」解耦这正是Traverse比单纯Foldable表达力更强的原因详见练习 15 的讨论Foldable无法构造新结构而Traverse通过保留结构可以扩展出Functor见 15.answer.md。五、练习 17 在 Traverse 方法族中的位置foldLeft不是孤立的一题它与练习 16reverse16.answer.md、练习 18fuse18.answer.md等共同构成mapAccum派生方法族def zipWithIndex: F[(A, Int)] // mapAccum 以 Int 为状态 fa.mapAccum(0)((a, s) ((a, s), s 1))(0) def reverse: F[A] // mapAccum 以 List 为状态 fa.mapAccum(fa.toList.reverse)((_, as) (as.head, as.tail))(0) def zipB: F[(A, B)] // mapAccum 消费另一结构的列表 fa.mapAccum(fb.toList): case (a, Nil) sys.error(zip: Incompatible shapes.) case (a, b :: bs) ((a, b), bs) ._1以上均出自 answers 版 Traverse.scala。可以看出mapAccum是练习 14 引入的「通用累积引擎」后续多个练习都在它之上各取所需zipWithIndex用整数计数、reverse用列表弹栈、zip用列表配对。练习 17 的foldLeft则把累积目标泛化到任意类型B是这条方法链中抽象程度最高的一环。六、验证与测试套件的对照仓库中虽未为 applicative 章节单独建测试文件但foldLeft的语义约定在 monoids 章节的测试中得到过严格验证。FoldableSuite.scala 对List、IndexedSeq、LazyList、Tree、Option五类结构分别断言foldLeft、foldRight、foldMap与标准实现结果一致例如assertEquals(list.foldLeft(0)((acc, s) s.length acc), expected)这为理解练习 17 提供了两个实用视角语义基准foldLeft必须满足「从初始值acc出发按从左到右的顺序逐个应用f」的既定语义练习 17 的mapAccum实现与这些被测试验证过的行为完全一致一致性保障由于Traverse的foldLeft是Foldable抽象方法的覆盖实现任何Traverse实例List、Option、Tree、Map[K, _]见 answers 版 Traverse.scala都能自动获得行为正确的折叠能力无需为每个容器单独编写foldLeft。七、动手验证与延伸思考想在本仓库中亲自验证这个实现可以按 README.md 的说明操作# 编译全部练习题与答案 $ scala-cli compile . # 进入 REPL 交互验证 $ scala-cli console . scala import fpinscala.answers.applicative.Traverse.* scala import fpinscala.answers.applicative.Traverse.given scala List(1, 2, 3).foldLeft(0)(_ _) // 期望 6 scala List(a, b, c).foldLeft()(_ _) // 期望 abc需要注意练习 17 的foldLeft定义在trait Traverse的扩展方法中必须在作用域内引入对应的given实例如listTraverse才能对具体类型调用。延伸思考能否用foldRight类似地实现foldLeft可以但需要借助端函数幺半群endoMonoid等技巧Monoid.scala 展示了Foldable默认实现的做法对比两种路线能更清楚mapAccum的优势。mapAccum是否比手写递归更高效二者都是线性复杂度mapAccum的价值在于复用性与可组合性——zip、reverse、foldLeft共享同一引擎减少了每个操作的重复逻辑。为什么mapAccum返回(F[B], S)而foldLeft只取状态因为foldLeft不关心重建结构B部分恒为()只关心累积的最终状态这正是「累积」与「结构变换」两个维度的分离也是Traverse设计中的关键洞察。结语练习 17 虽然只有短短一行实现却浓缩了 fpinscala 第 12 章的核心思想用State应用函子把「遍历」与「累积」统一到mapAccum这一个原语上让Traverse优雅地继承Foldable的全部折叠能力。理解foldLeft与toList的对称实现是掌握zipWithIndex、reverse、zip、fuse等一系列衍生操作的最佳起点也为后续练习 20 的composeM借助Traverse[H]实现 Monad 组合见 20.answer.md打下了基础。赞分享示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载相关推荐fpinscala 练习 16 精解用 mapAccum 与 List 栈实现 Traverse 的 reversefpinscala 练习 16 精解用 mapAccum 与 List 栈实现 Traverse 的 reverse 导读 本文围绕《Functional P示例工程用 mapAccum 实现 foldLeftfpinscala Traverse 练习 17 的答案精讲用 mapAccum 实现 foldLeftfpinscala Traverse 练习 17 的答案精讲 导读 本文讲解《Functional Program示例工程fpinscala 第 12 章练习 16 精解借助 List 栈与 mapAccum 为任意 Traverse 实现 reversefpinscala 第 12 章练习 16 精解借助 List 栈与 mapAccum 为任意 Traverse 实现 reverse 导读 本文围绕 fpi示例工程上一篇yomiyasu 推敲实战REST 与 GraphQL 技术选型文档正式文体的改写对照与语料验证下一篇PCRE 正規表達式完整入門指南從超字元到實戰解析 Apache 存取日誌zh-tw 版创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
分析器构建闭环训练：从文法改写到Python实现)
![[从入门到入土!!!] Ubuntu20.04 系统开发环境配置（系统配置，显卡驱动，CUDA，ROS，VSCode，Anaconda等）](http://pic.xiahunao.cn/yaotu/[从入门到入土!!!] Ubuntu20.04 系统开发环境配置（系统配置，显卡驱动，CUDA，ROS，VSCode，Anaconda等）)
