示例工程【免费下载链接】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 的 applicative 章节第 13 题完整讲解如何为List、Option、Tree、Map[K, _]四种类型实现Traverse实例。题目给出的提示是跟随类型走Follow the types我们将从traverse的签名出发逐步推导出每种结构唯一合理的实现并对照仓库中的参考答案与源码说明这些实例如何与map、foldMap、sequence、mapAccum等操作互相打通。读完本文你将掌握类型驱动实现的方法论并能独立为自定义容器类型写出正确的Traverse实例。一、题目定位13 题在 Traverse 练习线中的位置1.1 练习与参考答案的对应关系仓库将练习与答案分开存放练习文件src/main/scala/fpinscala/exercises/applicative/Traverse.scala其中object Traverse内的四个given全部是???占位参考答案文件src/main/scala/fpinscala/answers/applicative/Traverse.scala给出了完整实现配套讲解answerkey/applicative/13.answer.md 与 answerkey/applicative/13.hint.md。第 13 题的 hint 只有一句话Follow the types. There is generally only one sensible implementation that typechecks.跟随类型走通常只有一种能通过类型检查的合理解法。这正是函数式编程中类型即文档思想的体现只要类型签名足够精确实现几乎是被类型逼出来的。1.2 前置Traverse 类型类的最小定义在动手实现具体实例前先看Traverse抽象本身answers/applicative/Traverse.scalatrait 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 extension [G[_]: Applicative, A](fga: F[G[A]]) def sequence: G[F[A]] fga.traverse(ga ga)关键点Traverse[F]同时继承Functor[F]与Foldable[F]即一个可遍历容器天然既是函子又是可折叠结构traverse接受一个把元素A送入效应上下文G的函数f: A G[B]并把整个结构F[A]翻转成G[F[B]]——容器与效应发生了位置互换默认实现里traverse用map sequence表达sequence又用traverse表达。因此一个具体的Traverse实例只需实现traverse一个方法map、sequence乃至foldMap、toList都会随之获得详见下文打通一节。正因为如此第 13 题要为四个类型各写一个traverse的given实例。下面逐一拆解。二、listTraverse用foldRight自右向左组合2.1 答案原文given listTraverse: Traverse[List] with extension A override def traverse[G[_]: Applicative, B](f: A G[B]): G[List[B]] val g summon[Applicative[G]] as.foldRight(g.unit(List[B]()))((a, acc) f(a).map2(acc)(_ :: _))2.2 类型驱动的推导traverse要求返回G[List[B]]而输入是List[A]。对列表来说最自然的折叠工具是foldRight。我们需要初始值空列表对应的效应值g.unit(List[B]())类型为G[List[B]]组合函数对每个元素a: A先计算f(a): G[B]再与已累积的acc: G[List[B]]用map2拼接_ :: _把新元素放在头部。map2来自 Applicative.scalaextension A def map2B, C(f: (A, B) C): F[C] apply(apply(unit(f.curried))(fa))(fb)由于是foldRight元素从右往左处理最终List中元素的相对顺序与原始列表一致——这正是保持结构的体现。2.3 一个观察traverse与Applicative.traverse的关系注意 Applicative.scala 中已经有一个针对List的traversedef traverseA,B(f: A F[B]): F[List[B]] as.foldRight(unit(List[B]()))((a, acc) f(a).map2(acc)(_ :: _))二者结构完全一致。区别在于Applicative.traverse是给定一个Applicative[F]遍历List而Traverse[List]的traverse是List这个容器自己支持在任意Applicative[G]中遍历。当G取某个具体类型如Option、State、Validated时同样的foldRight map2模式会反复出现这正是第 12 题sequenceMap与本题共用的累加器 map2套路。三、optionTraverse模式匹配两分支3.1 答案原文given optionTraverse: Traverse[Option] with extension A override def traverse[G[_]: Applicative, B](f: A G[B]): G[Option[B]] oa match case Some(a) f(a).map(Some(_)) case None summon[Applicative[G]].unit(None)3.2 两个分支的类型推理Option[A]只有两种形态模式匹配后类型自然收窄Some(a)手里有一个A直接调用f(a): G[B]再用map包回Some(_)得到G[Option[B]]None没有任何元素可遍历唯一能产出的就是G[Option[B]]的空值——即summon[Applicative[G]].unit(None)。这里map是Applicative提供的能力Applicative.scaladef mapB: F[B] apply(unit(f))(fa)unit则是Applicative的核心抽象方法。对Option而言遍历None恒得到unit(None)配合Either、Validated等效应这个行为天然表达了短路或成功/失败的语义。四、treeTraverse递归遍历树4.1 答案原文given treeTraverse: Traverse[Tree] new: extension A override def traverse[G[_]: Applicative, B](f: A G[B]): G[Tree[B]] f(ta.head).map2(ta.tail.traverse(a a.traverse(f)))(Tree(_, _))4.2 树的形状决定了递归结构Tree在 answers/applicative/Traverse.scala 中定义case class TreeA即头元素 子树列表。因此遍历一棵树需要两步对头元素调用f(ta.head): G[B]对tail中的每棵子树递归调用a.traverse(f)得到一个G[List[Tree[B]]]这里用到了List的traverse即上一节实现的listTraverse用map2把两者重新组合为Tree(_, _)类型恰为G[Tree[B]]。这里体现了Traverse的可组合性实现Tree的遍历时我们直接复用了List的遍历能力。外层表达式ta.tail.traverse(...)调用的是List的Traverse实例通过上下文提供的given自动解析而内层a.traverse(f)递归调用的是当前Tree实例自身。注意这里的given treeTraverse使用了 new:的写法而不是with——因为Traverse[Tree]的Traverse特质带有self 自引用别名trait Traverse[F[_]] extends Functor[F], Foldable[F]: self 匿名类实例化时必须用new:语法。这是 Scala 3 中带自类型别名特质的标准实例化方式练习文件中同样保留了这一写法exercises/applicative/Traverse.scala。五、mapTraversefoldLeft 逐键累积5.1 答案原文given mapTraverse[K]: Traverse[Map[K, _]] with extension A override def traverse[G[_]: Applicative, B](f: A G[B]): G[Map[K, B]] m.foldLeft(summon[Applicative[G]].unit(Map.empty[K, B])): case (acc, (k, a)) acc.map2(f(a))((m, b) m (k - b))5.2 细节剖析Map与List不同它没有天然的头部插入方向因此这里选用foldLeft从空 Map 出发逐个键累积初始值g.unit(Map.empty[K, B])每个键值对(k, a)计算f(a): G[B]与当前累积acc: G[Map[K, B]]用map2合并(m, b) m (k - b)把转换后的值按原键写回。几点值得注意Map[K, _]与Traverse[Map[K, _]]实例带类型参数K且容器参数写为Map[K, _]即固定键类型、任意值类型的容器。这与Foldable、Functor对Map的处理思路一致——键是结构的骨架遍历只作用于值。与sequenceMap的呼应answerkey/applicative/12.answer.md 中sequenceMap的实现是def sequenceMapK, V: F[Map[K, V]] ofv.foldLeft(unit(Map.empty[K, V])): case (acc, (k, fv)) acc.map2(fv)((m, v) m (k - v))可以看到mapTraverse就是sequenceMap的推广sequenceMap翻转的是值已经是效应的 MapmapTraverse翻转的是值经过f进入效应的 Map。两者共享同一套foldLeft map2累积模式这再次印证 hint 中只有一种合理实现的判断——类型签名几乎唯一地决定了算法形状。六、Follow the types如何从签名猜出实现第 13 题 hint 的Follow the types值得展开成方法论。以optionTraverse为例签名要求def traverse[G[_]: Applicative, B](f: A G[B]): G[Option[B]]输入要么是Some(a)要么是None若是Some(a)能产生G[B]的手段只有f(a)要得到G[Option[B]]只能map(Some(_))若是None没有元素可用能产生任意G[X]的手段只有summon[Applicative[G]].unit(...)而None是Option唯一的空值所以是unit(None)。listTraverse同理空列表对应unit(List[B]())非空列表的元素要逐个经过f且最终要保持顺序这要求f(a)与已遍历部分用map2组合——foldRight保证顺序_ :: _保证拼接。这类推导在整条练习线中反复出现例如 answerkey/applicative/14.answer.md 用Id作为最简Applicative把traverse退化成mapanswerkey/applicative/15.answer.md 讨论Iteration为何是可折叠但不可映射因为它无法从内部重建结构answerkey/applicative/16.answer.md 与 answerkey/applicative/17.answer.md 又用mapAccum实现reverse与foldLeft。可以说第 13 题是整条类型驱动实现训练线的枢纽。七、打通一个traverse实例如何带出整套操作7.1map与foldMap都是特化因为Traverse[F]继承Functor[F]与Foldable[F]且只强制实现traverse那么map与foldMap必须有默认推导。参考答案answers/applicative/Traverse.scalatype Id[A] A object Id: given idMonad: Monad[Id] with def unitA a extension A override def flatMapB: B f(a) extension A def mapB: F[B] fa.traverseId, B(using Id.idMonad) override def foldMapB: Monoid: B fa.traverse[Const[B, _], Nothing](f)map 在Id效应中traverseId[A] A遍历时不携带任何额外效应结果仍是原结构——这正是一个Functor的map。这也为traverse提供了律则线索用Id特化得到的map必须满足函子律foldMap 在Const效应中traverseConst[M, A] MConst的Applicative实例Applicative.scala把unit定义为m.empty、把apply定义为m.combine于是遍历过程退化为用 Monoid 折叠所有元素。同理sequence已由抽象类给出默认实现toList、zipWithIndex、reverse、zip等则建立在mapAccum内部用State效应traverse之上answers/applicative/Traverse.scala。因此第 13 题写完四个traverse后四种容器立即免费获得map、foldMap、toList、zipWithIndex、reverse、zip等一整套操作。7.2Monad侧对Traverse的依赖Traverse的价值还不止于自身在 answers/applicative/Monad.scala 中composeM要组合两个 MonadG与H正是依靠T: Traverse[H]对内层结构做遍历def composeM[G[_], H[_]](using G: Monad[G], H: Monad[H], T: Traverse[H]): Monad[[x] G[H[x]]] new: def unitA: G[H[A]] G.unit(H.unit(a)) extension A override def flatMapB: G[H[B]] G.flatMap(gha)(ha G.map(T.traverse(ha)(f))(H.join))而 answerkey/applicative/11.answer.md 正说明没有Traverse提供交换内外层的能力Monad 组合是写不出来的。第 13 题实现的listTraverse等实例就是让composeM得以落地的具体砖石。八、实例的验证与使用8.1 测试证据仓库测试 src/test/scala/fpinscala/exercises/monads/MonadSuite.scala 覆盖了Monad.sequence与Monad.traversetest(Monad.sequence)(genIntList ** genRNG): case intList ** rng val tm genMonad(rng) import tm.* val listMonad monad.sequence(intList.map(Gen.unit)) assertFs(listMonad, pure(intList)) test(Monad.traverse)(genIntList ** genRNG): case intList ** rng val tm genMonad(rng) import tm.* val listMonad monad.traverse(intList)(Gen.unit) assertFs(listMonad, pure(intList))测试用属性化方式验证把Gen.unit作为f遍历任意整数列表结果应与直接提升整个列表等价。这是traverse恒等律traverse(unit)保持结构的实证也从侧面验证了Traverse[List]实例的行为正确性。8.2 快速上手在 Scala REPL / 测试中试用given实例定义在Traverse伴生对象中answers/applicative/Traverse.scalaScala 3 会自动解析。例如把Option当作效应遍历Listimport fpinscala.answers.applicative.Traverse.given // List 的 Traverse 在 Option 效应中全有则 Some任一缺失则 None List(1, 2, 3).traverse(a Some(a * 2)) // Some(List(2, 4, 6)) List(1, 2, 3).traverse(a if a 1 then Some(a) else None) // None用Validated效应遍历可以累积所有错误用State效应遍历可以实现zipWithIndex等带状态的操作——这些都能在 answers/applicative/Applicative.scala 中找到现成的Applicative实例optionMonad、validatedApplicative、stateMonad等直接配合使用。九、小结第 13 题表面上是写四个given实则是练习类型驱动的推导容器核心手法关键要点List[A]foldRightmap2_ :: _自右向左保持元素顺序Option[A]模式匹配两个分支Some走mapNone走unitTree[A]递归 复用List的遍历map2重组头与子树Map[K, A]foldLeftmap2m (k - b)逐键累积只遍历值而 hint 中的 Follow the types 不是空话以上四个实现中每一步操作的类型都严格收敛几乎不存在第二种能通过类型检查的方案。掌握了这套推导再结合 answers/applicative/Traverse.scala 中Id、Const、State等特化技巧你就能为任何形状的数据结构写出既正确又优雅的Traverse实例并把map、fold、zip、reverse等能力一次性地全部解锁。赞分享示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载相关推荐fpinscala 第 6 章 Applicative 练习 6用 Monoid 为 Validated 实现错误累积的 Applicative 实例fpinscala 第 6 章 Applicative 练习 6用 Monoid 为 Validated 实现错误累积的 Applicative 实例 本文围示例工程fpinscala 精讲用 Applicative 的 traverse/sequence 实现列表转置第 12 章练习 04fpinscala 精讲用 Applicative 的 traverse/sequence 实现列表转置第 12 章练习 04 导读 本篇文章围绕 fpi示例工程fpinscala 练习 12.8 详解用 Applicative.product 组合两个 Applicative 实例fpinscala 练习 12.8 详解用 Applicative.product 组合两个 Applicative 实例 本篇技术指南聚焦《Function示例工程上一篇终极Tortoise ORM单元测试指南异步测试框架集成完整教程下一篇如何快速搭建Enatega外卖系统本地运行顾客App、骑手App与管理面板的完整教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 fpinscala Applicative 练习 13 全解：为 List、Option、Tree、Map 实现 Traverse 实例
示例工程【免费下载链接】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 的 applicative 章节第 13 题完整讲解如何为List、Option、Tree、Map[K, _]四种类型实现Traverse实例。题目给出的提示是跟随类型走Follow the types我们将从traverse的签名出发逐步推导出每种结构唯一合理的实现并对照仓库中的参考答案与源码说明这些实例如何与map、foldMap、sequence、mapAccum等操作互相打通。读完本文你将掌握类型驱动实现的方法论并能独立为自定义容器类型写出正确的Traverse实例。一、题目定位13 题在 Traverse 练习线中的位置1.1 练习与参考答案的对应关系仓库将练习与答案分开存放练习文件src/main/scala/fpinscala/exercises/applicative/Traverse.scala其中object Traverse内的四个given全部是???占位参考答案文件src/main/scala/fpinscala/answers/applicative/Traverse.scala给出了完整实现配套讲解answerkey/applicative/13.answer.md 与 answerkey/applicative/13.hint.md。第 13 题的 hint 只有一句话Follow the types. There is generally only one sensible implementation that typechecks.跟随类型走通常只有一种能通过类型检查的合理解法。这正是函数式编程中类型即文档思想的体现只要类型签名足够精确实现几乎是被类型逼出来的。1.2 前置Traverse 类型类的最小定义在动手实现具体实例前先看Traverse抽象本身answers/applicative/Traverse.scalatrait 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 extension [G[_]: Applicative, A](fga: F[G[A]]) def sequence: G[F[A]] fga.traverse(ga ga)关键点Traverse[F]同时继承Functor[F]与Foldable[F]即一个可遍历容器天然既是函子又是可折叠结构traverse接受一个把元素A送入效应上下文G的函数f: A G[B]并把整个结构F[A]翻转成G[F[B]]——容器与效应发生了位置互换默认实现里traverse用map sequence表达sequence又用traverse表达。因此一个具体的Traverse实例只需实现traverse一个方法map、sequence乃至foldMap、toList都会随之获得详见下文打通一节。正因为如此第 13 题要为四个类型各写一个traverse的given实例。下面逐一拆解。二、listTraverse用foldRight自右向左组合2.1 答案原文given listTraverse: Traverse[List] with extension A override def traverse[G[_]: Applicative, B](f: A G[B]): G[List[B]] val g summon[Applicative[G]] as.foldRight(g.unit(List[B]()))((a, acc) f(a).map2(acc)(_ :: _))2.2 类型驱动的推导traverse要求返回G[List[B]]而输入是List[A]。对列表来说最自然的折叠工具是foldRight。我们需要初始值空列表对应的效应值g.unit(List[B]())类型为G[List[B]]组合函数对每个元素a: A先计算f(a): G[B]再与已累积的acc: G[List[B]]用map2拼接_ :: _把新元素放在头部。map2来自 Applicative.scalaextension A def map2B, C(f: (A, B) C): F[C] apply(apply(unit(f.curried))(fa))(fb)由于是foldRight元素从右往左处理最终List中元素的相对顺序与原始列表一致——这正是保持结构的体现。2.3 一个观察traverse与Applicative.traverse的关系注意 Applicative.scala 中已经有一个针对List的traversedef traverseA,B(f: A F[B]): F[List[B]] as.foldRight(unit(List[B]()))((a, acc) f(a).map2(acc)(_ :: _))二者结构完全一致。区别在于Applicative.traverse是给定一个Applicative[F]遍历List而Traverse[List]的traverse是List这个容器自己支持在任意Applicative[G]中遍历。当G取某个具体类型如Option、State、Validated时同样的foldRight map2模式会反复出现这正是第 12 题sequenceMap与本题共用的累加器 map2套路。三、optionTraverse模式匹配两分支3.1 答案原文given optionTraverse: Traverse[Option] with extension A override def traverse[G[_]: Applicative, B](f: A G[B]): G[Option[B]] oa match case Some(a) f(a).map(Some(_)) case None summon[Applicative[G]].unit(None)3.2 两个分支的类型推理Option[A]只有两种形态模式匹配后类型自然收窄Some(a)手里有一个A直接调用f(a): G[B]再用map包回Some(_)得到G[Option[B]]None没有任何元素可遍历唯一能产出的就是G[Option[B]]的空值——即summon[Applicative[G]].unit(None)。这里map是Applicative提供的能力Applicative.scaladef mapB: F[B] apply(unit(f))(fa)unit则是Applicative的核心抽象方法。对Option而言遍历None恒得到unit(None)配合Either、Validated等效应这个行为天然表达了短路或成功/失败的语义。四、treeTraverse递归遍历树4.1 答案原文given treeTraverse: Traverse[Tree] new: extension A override def traverse[G[_]: Applicative, B](f: A G[B]): G[Tree[B]] f(ta.head).map2(ta.tail.traverse(a a.traverse(f)))(Tree(_, _))4.2 树的形状决定了递归结构Tree在 answers/applicative/Traverse.scala 中定义case class TreeA即头元素 子树列表。因此遍历一棵树需要两步对头元素调用f(ta.head): G[B]对tail中的每棵子树递归调用a.traverse(f)得到一个G[List[Tree[B]]]这里用到了List的traverse即上一节实现的listTraverse用map2把两者重新组合为Tree(_, _)类型恰为G[Tree[B]]。这里体现了Traverse的可组合性实现Tree的遍历时我们直接复用了List的遍历能力。外层表达式ta.tail.traverse(...)调用的是List的Traverse实例通过上下文提供的given自动解析而内层a.traverse(f)递归调用的是当前Tree实例自身。注意这里的given treeTraverse使用了 new:的写法而不是with——因为Traverse[Tree]的Traverse特质带有self 自引用别名trait Traverse[F[_]] extends Functor[F], Foldable[F]: self 匿名类实例化时必须用new:语法。这是 Scala 3 中带自类型别名特质的标准实例化方式练习文件中同样保留了这一写法exercises/applicative/Traverse.scala。五、mapTraversefoldLeft 逐键累积5.1 答案原文given mapTraverse[K]: Traverse[Map[K, _]] with extension A override def traverse[G[_]: Applicative, B](f: A G[B]): G[Map[K, B]] m.foldLeft(summon[Applicative[G]].unit(Map.empty[K, B])): case (acc, (k, a)) acc.map2(f(a))((m, b) m (k - b))5.2 细节剖析Map与List不同它没有天然的头部插入方向因此这里选用foldLeft从空 Map 出发逐个键累积初始值g.unit(Map.empty[K, B])每个键值对(k, a)计算f(a): G[B]与当前累积acc: G[Map[K, B]]用map2合并(m, b) m (k - b)把转换后的值按原键写回。几点值得注意Map[K, _]与Traverse[Map[K, _]]实例带类型参数K且容器参数写为Map[K, _]即固定键类型、任意值类型的容器。这与Foldable、Functor对Map的处理思路一致——键是结构的骨架遍历只作用于值。与sequenceMap的呼应answerkey/applicative/12.answer.md 中sequenceMap的实现是def sequenceMapK, V: F[Map[K, V]] ofv.foldLeft(unit(Map.empty[K, V])): case (acc, (k, fv)) acc.map2(fv)((m, v) m (k - v))可以看到mapTraverse就是sequenceMap的推广sequenceMap翻转的是值已经是效应的 MapmapTraverse翻转的是值经过f进入效应的 Map。两者共享同一套foldLeft map2累积模式这再次印证 hint 中只有一种合理实现的判断——类型签名几乎唯一地决定了算法形状。六、Follow the types如何从签名猜出实现第 13 题 hint 的Follow the types值得展开成方法论。以optionTraverse为例签名要求def traverse[G[_]: Applicative, B](f: A G[B]): G[Option[B]]输入要么是Some(a)要么是None若是Some(a)能产生G[B]的手段只有f(a)要得到G[Option[B]]只能map(Some(_))若是None没有元素可用能产生任意G[X]的手段只有summon[Applicative[G]].unit(...)而None是Option唯一的空值所以是unit(None)。listTraverse同理空列表对应unit(List[B]())非空列表的元素要逐个经过f且最终要保持顺序这要求f(a)与已遍历部分用map2组合——foldRight保证顺序_ :: _保证拼接。这类推导在整条练习线中反复出现例如 answerkey/applicative/14.answer.md 用Id作为最简Applicative把traverse退化成mapanswerkey/applicative/15.answer.md 讨论Iteration为何是可折叠但不可映射因为它无法从内部重建结构answerkey/applicative/16.answer.md 与 answerkey/applicative/17.answer.md 又用mapAccum实现reverse与foldLeft。可以说第 13 题是整条类型驱动实现训练线的枢纽。七、打通一个traverse实例如何带出整套操作7.1map与foldMap都是特化因为Traverse[F]继承Functor[F]与Foldable[F]且只强制实现traverse那么map与foldMap必须有默认推导。参考答案answers/applicative/Traverse.scalatype Id[A] A object Id: given idMonad: Monad[Id] with def unitA a extension A override def flatMapB: B f(a) extension A def mapB: F[B] fa.traverseId, B(using Id.idMonad) override def foldMapB: Monoid: B fa.traverse[Const[B, _], Nothing](f)map 在Id效应中traverseId[A] A遍历时不携带任何额外效应结果仍是原结构——这正是一个Functor的map。这也为traverse提供了律则线索用Id特化得到的map必须满足函子律foldMap 在Const效应中traverseConst[M, A] MConst的Applicative实例Applicative.scala把unit定义为m.empty、把apply定义为m.combine于是遍历过程退化为用 Monoid 折叠所有元素。同理sequence已由抽象类给出默认实现toList、zipWithIndex、reverse、zip等则建立在mapAccum内部用State效应traverse之上answers/applicative/Traverse.scala。因此第 13 题写完四个traverse后四种容器立即免费获得map、foldMap、toList、zipWithIndex、reverse、zip等一整套操作。7.2Monad侧对Traverse的依赖Traverse的价值还不止于自身在 answers/applicative/Monad.scala 中composeM要组合两个 MonadG与H正是依靠T: Traverse[H]对内层结构做遍历def composeM[G[_], H[_]](using G: Monad[G], H: Monad[H], T: Traverse[H]): Monad[[x] G[H[x]]] new: def unitA: G[H[A]] G.unit(H.unit(a)) extension A override def flatMapB: G[H[B]] G.flatMap(gha)(ha G.map(T.traverse(ha)(f))(H.join))而 answerkey/applicative/11.answer.md 正说明没有Traverse提供交换内外层的能力Monad 组合是写不出来的。第 13 题实现的listTraverse等实例就是让composeM得以落地的具体砖石。八、实例的验证与使用8.1 测试证据仓库测试 src/test/scala/fpinscala/exercises/monads/MonadSuite.scala 覆盖了Monad.sequence与Monad.traversetest(Monad.sequence)(genIntList ** genRNG): case intList ** rng val tm genMonad(rng) import tm.* val listMonad monad.sequence(intList.map(Gen.unit)) assertFs(listMonad, pure(intList)) test(Monad.traverse)(genIntList ** genRNG): case intList ** rng val tm genMonad(rng) import tm.* val listMonad monad.traverse(intList)(Gen.unit) assertFs(listMonad, pure(intList))测试用属性化方式验证把Gen.unit作为f遍历任意整数列表结果应与直接提升整个列表等价。这是traverse恒等律traverse(unit)保持结构的实证也从侧面验证了Traverse[List]实例的行为正确性。8.2 快速上手在 Scala REPL / 测试中试用given实例定义在Traverse伴生对象中answers/applicative/Traverse.scalaScala 3 会自动解析。例如把Option当作效应遍历Listimport fpinscala.answers.applicative.Traverse.given // List 的 Traverse 在 Option 效应中全有则 Some任一缺失则 None List(1, 2, 3).traverse(a Some(a * 2)) // Some(List(2, 4, 6)) List(1, 2, 3).traverse(a if a 1 then Some(a) else None) // None用Validated效应遍历可以累积所有错误用State效应遍历可以实现zipWithIndex等带状态的操作——这些都能在 answers/applicative/Applicative.scala 中找到现成的Applicative实例optionMonad、validatedApplicative、stateMonad等直接配合使用。九、小结第 13 题表面上是写四个given实则是练习类型驱动的推导容器核心手法关键要点List[A]foldRightmap2_ :: _自右向左保持元素顺序Option[A]模式匹配两个分支Some走mapNone走unitTree[A]递归 复用List的遍历map2重组头与子树Map[K, A]foldLeftmap2m (k - b)逐键累积只遍历值而 hint 中的 Follow the types 不是空话以上四个实现中每一步操作的类型都严格收敛几乎不存在第二种能通过类型检查的方案。掌握了这套推导再结合 answers/applicative/Traverse.scala 中Id、Const、State等特化技巧你就能为任何形状的数据结构写出既正确又优雅的Traverse实例并把map、fold、zip、reverse等能力一次性地全部解锁。赞分享示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载相关推荐fpinscala 第 6 章 Applicative 练习 6用 Monoid 为 Validated 实现错误累积的 Applicative 实例fpinscala 第 6 章 Applicative 练习 6用 Monoid 为 Validated 实现错误累积的 Applicative 实例 本文围示例工程fpinscala 精讲用 Applicative 的 traverse/sequence 实现列表转置第 12 章练习 04fpinscala 精讲用 Applicative 的 traverse/sequence 实现列表转置第 12 章练习 04 导读 本篇文章围绕 fpi示例工程fpinscala 练习 12.8 详解用 Applicative.product 组合两个 Applicative 实例fpinscala 练习 12.8 详解用 Applicative.product 组合两个 Applicative 实例 本篇技术指南聚焦《Function示例工程上一篇终极Tortoise ORM单元测试指南异步测试框架集成完整教程下一篇如何快速搭建Enatega外卖系统本地运行顾客App、骑手App与管理面板的完整教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考