示例工程【免費(fèi)下載鏈接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala項(xiàng)目地址https://gitcode.com/gh_mirrors/fp/fpinscala點(diǎn)擊查看免費(fèi)下載導(dǎo)讀本文聚焦《Functional Programming in Scala》配套倉(cāng)庫(kù) fpinscala 的 applicative 章節(jié)第 13 題完整講解如何為L(zhǎng)ist、Option、Tree、Map[K, _]四種類型實(shí)現(xiàn)Traverse實(shí)例。題目給出的提示是跟隨類型走Follow the types我們將從traverse的簽名出發(fā)逐步推導(dǎo)出每種結(jié)構(gòu)唯一合理的實(shí)現(xiàn)并對(duì)照倉(cāng)庫(kù)中的參考答案與源碼說(shuō)明這些實(shí)例如何與map、foldMap、sequence、mapAccum等操作互相打通。讀完本文你將掌握類型驅(qū)動(dòng)實(shí)現(xiàn)的方法論并能獨(dú)立為自定義容器類型寫(xiě)出正確的Traverse實(shí)例。一、題目定位13 題在 Traverse 練習(xí)線中的位置1.1 練習(xí)與參考答案的對(duì)應(yīng)關(guān)系倉(cāng)庫(kù)將練習(xí)與答案分開(kāi)存放練習(xí)文件src/main/scala/fpinscala/exercises/applicative/Traverse.scala其中object Traverse內(nèi)的四個(gè)given全部是???占位參考答案文件src/main/scala/fpinscala/answers/applicative/Traverse.scala給出了完整實(shí)現(xiàn)配套講解answerkey/applicative/13.answer.md 與 answerkey/applicative/13.hint.md。第 13 題的 hint 只有一句話Follow the types. There is generally only one sensible implementation that typechecks.跟隨類型走通常只有一種能通過(guò)類型檢查的合理解法。這正是函數(shù)式編程中類型即文檔思想的體現(xiàn)只要類型簽名足夠精確實(shí)現(xiàn)幾乎是被類型逼出來(lái)的。1.2 前置Traverse 類型類的最小定義在動(dòng)手實(shí)現(xiàn)具體實(shí)例前先看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)關(guān)鍵點(diǎn)Traverse[F]同時(shí)繼承Functor[F]與Foldable[F]即一個(gè)可遍歷容器天然既是函子又是可折疊結(jié)構(gòu)traverse接受一個(gè)把元素A送入效應(yīng)上下文G的函數(shù)f: A G[B]并把整個(gè)結(jié)構(gòu)F[A]翻轉(zhuǎn)成G[F[B]]——容器與效應(yīng)發(fā)生了位置互換默認(rèn)實(shí)現(xiàn)里traverse用map sequence表達(dá)sequence又用traverse表達(dá)。因此一個(gè)具體的Traverse實(shí)例只需實(shí)現(xiàn)traverse一個(gè)方法map、sequence乃至foldMap、toList都會(huì)隨之獲得詳見(jiàn)下文打通一節(jié)。正因?yàn)槿绱说?13 題要為四個(gè)類型各寫(xiě)一個(gè)traverse的given實(shí)例。下面逐一拆解。二、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 類型驅(qū)動(dòng)的推導(dǎo)traverse要求返回G[List[B]]而輸入是List[A]。對(duì)列表來(lái)說(shuō)最自然的折疊工具是foldRight。我們需要初始值空列表對(duì)應(yīng)的效應(yīng)值g.unit(List[B]())類型為G[List[B]]組合函數(shù)對(duì)每個(gè)元素a: A先計(jì)算f(a): G[B]再與已累積的acc: G[List[B]]用map2拼接_ :: _把新元素放在頭部。map2來(lái)自 Applicative.scalaextension A def map2B, C(f: (A, B) C): F[C] apply(apply(unit(f.curried))(fa))(fb)由于是foldRight元素從右往左處理最終List中元素的相對(duì)順序與原始列表一致——這正是保持結(jié)構(gòu)的體現(xiàn)。2.3 一個(gè)觀察traverse與Applicative.traverse的關(guān)系注意 Applicative.scala 中已經(jīng)有一個(gè)針對(duì)List的traversedef traverseA,B(f: A F[B]): F[List[B]] as.foldRight(unit(List[B]()))((a, acc) f(a).map2(acc)(_ :: _))二者結(jié)構(gòu)完全一致。區(qū)別在于Applicative.traverse是給定一個(gè)Applicative[F]遍歷List而Traverse[List]的traverse是List這個(gè)容器自己支持在任意Applicative[G]中遍歷。當(dāng)G取某個(gè)具體類型如Option、State、Validated時(shí)同樣的foldRight map2模式會(huì)反復(fù)出現(xiàn)這正是第 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 兩個(gè)分支的類型推理Option[A]只有兩種形態(tài)模式匹配后類型自然收窄Some(a)手里有一個(gè)A直接調(diào)用f(a): G[B]再用map包回Some(_)得到G[Option[B]]None沒(méi)有任何元素可遍歷唯一能產(chǎn)出的就是G[Option[B]]的空值——即summon[Applicative[G]].unit(None)。這里map是Applicative提供的能力Applicative.scaladef mapB: F[B] apply(unit(f))(fa)unit則是Applicative的核心抽象方法。對(duì)Option而言遍歷None恒得到unit(None)配合Either、Validated等效應(yīng)這個(gè)行為天然表達(dá)了短路或成功/失敗的語(yǔ)義。四、treeTraverse遞歸遍歷樹(shù)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 樹(shù)的形狀決定了遞歸結(jié)構(gòu)Tree在 answers/applicative/Traverse.scala 中定義case class TreeA即頭元素 子樹(shù)列表。因此遍歷一棵樹(shù)需要兩步對(duì)頭元素調(diào)用f(ta.head): G[B]對(duì)tail中的每棵子樹(shù)遞歸調(diào)用a.traverse(f)得到一個(gè)G[List[Tree[B]]]這里用到了List的traverse即上一節(jié)實(shí)現(xiàn)的listTraverse用map2把兩者重新組合為Tree(_, _)類型恰為G[Tree[B]]。這里體現(xiàn)了Traverse的可組合性實(shí)現(xiàn)Tree的遍歷時(shí)我們直接復(fù)用了List的遍歷能力。外層表達(dá)式ta.tail.traverse(...)調(diào)用的是List的Traverse實(shí)例通過(guò)上下文提供的given自動(dòng)解析而內(nèi)層a.traverse(f)遞歸調(diào)用的是當(dāng)前Tree實(shí)例自身。注意這里的given treeTraverse使用了 new:的寫(xiě)法而不是with——因?yàn)門raverse[Tree]的Traverse特質(zhì)帶有self 自引用別名trait Traverse[F[_]] extends Functor[F], Foldable[F]: self 匿名類實(shí)例化時(shí)必須用new:語(yǔ)法。這是 Scala 3 中帶自類型別名特質(zhì)的標(biāo)準(zhǔn)實(shí)例化方式練習(xí)文件中同樣保留了這一寫(xiě)法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 細(xì)節(jié)剖析Map與List不同它沒(méi)有天然的頭部插入方向因此這里選用foldLeft從空 Map 出發(fā)逐個(gè)鍵累積初始值g.unit(Map.empty[K, B])每個(gè)鍵值對(duì)(k, a)計(jì)算f(a): G[B]與當(dāng)前累積acc: G[Map[K, B]]用map2合并(m, b) m (k - b)把轉(zhuǎn)換后的值按原鍵寫(xiě)回。幾點(diǎn)值得注意Map[K, _]與Traverse[Map[K, _]]實(shí)例帶類型參數(shù)K且容器參數(shù)寫(xiě)為Map[K, _]即固定鍵類型、任意值類型的容器。這與Foldable、Functor對(duì)Map的處理思路一致——鍵是結(jié)構(gòu)的骨架遍歷只作用于值。與sequenceMap的呼應(yīng)answerkey/applicative/12.answer.md 中sequenceMap的實(shí)現(xiàn)是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翻轉(zhuǎn)的是值已經(jīng)是效應(yīng)的 MapmapTraverse翻轉(zhuǎn)的是值經(jīng)過(guò)f進(jìn)入效應(yīng)的 Map。兩者共享同一套foldLeft map2累積模式這再次印證 hint 中只有一種合理實(shí)現(xiàn)的判斷——類型簽名幾乎唯一地決定了算法形狀。六、Follow the types如何從簽名猜出實(shí)現(xiàn)第 13 題 hint 的Follow the types值得展開(kāi)成方法論。以optionTraverse為例簽名要求def traverse[G[_]: Applicative, B](f: A G[B]): G[Option[B]]輸入要么是Some(a)要么是None若是Some(a)能產(chǎn)生G[B]的手段只有f(a)要得到G[Option[B]]只能map(Some(_))若是None沒(méi)有元素可用能產(chǎn)生任意G[X]的手段只有summon[Applicative[G]].unit(...)而None是Option唯一的空值所以是unit(None)。listTraverse同理空列表對(duì)應(yīng)unit(List[B]())非空列表的元素要逐個(gè)經(jīng)過(guò)f且最終要保持順序這要求f(a)與已遍歷部分用map2組合——foldRight保證順序_ :: _保證拼接。這類推導(dǎo)在整條練習(xí)線中反復(fù)出現(xiàn)例如 answerkey/applicative/14.answer.md 用Id作為最簡(jiǎn)Applicative把traverse退化成mapanswerkey/applicative/15.answer.md 討論Iteration為何是可折疊但不可映射因?yàn)樗鼰o(wú)法從內(nèi)部重建結(jié)構(gòu)answerkey/applicative/16.answer.md 與 answerkey/applicative/17.answer.md 又用mapAccum實(shí)現(xiàn)reverse與foldLeft。可以說(shuō)第 13 題是整條類型驅(qū)動(dòng)實(shí)現(xiàn)訓(xùn)練線的樞紐。七、打通一個(gè)traverse實(shí)例如何帶出整套操作7.1map與foldMap都是特化因?yàn)門raverse[F]繼承Functor[F]與Foldable[F]且只強(qiáng)制實(shí)現(xiàn)traverse那么map與foldMap必須有默認(rèn)推導(dǎo)。參考答案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效應(yīng)中traverseId[A] A遍歷時(shí)不攜帶任何額外效應(yīng)結(jié)果仍是原結(jié)構(gòu)——這正是一個(gè)Functor的map。這也為traverse提供了律則線索用Id特化得到的map必須滿足函子律foldMap 在Const效應(yīng)中traverseConst[M, A] MConst的Applicative實(shí)例Applicative.scala把unit定義為m.empty、把a(bǔ)pply定義為m.combine于是遍歷過(guò)程退化為用 Monoid 折疊所有元素。同理sequence已由抽象類給出默認(rèn)實(shí)現(xiàn)toList、zipWithIndex、reverse、zip等則建立在mapAccum內(nèi)部用State效應(yīng)traverse之上answers/applicative/Traverse.scala。因此第 13 題寫(xiě)完四個(gè)traverse后四種容器立即免費(fèi)獲得map、foldMap、toList、zipWithIndex、reverse、zip等一整套操作。7.2Monad側(cè)對(duì)Traverse的依賴Traverse的價(jià)值還不止于自身在 answers/applicative/Monad.scala 中composeM要組合兩個(gè) MonadG與H正是依靠T: Traverse[H]對(duì)內(nèi)層結(jié)構(gòu)做遍歷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 正說(shuō)明沒(méi)有Traverse提供交換內(nèi)外層的能力Monad 組合是寫(xiě)不出來(lái)的。第 13 題實(shí)現(xiàn)的listTraverse等實(shí)例就是讓composeM得以落地的具體磚石。八、實(shí)例的驗(yàn)證與使用8.1 測(cè)試證據(jù)倉(cāng)庫(kù)測(cè)試 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))測(cè)試用屬性化方式驗(yàn)證把Gen.unit作為f遍歷任意整數(shù)列表結(jié)果應(yīng)與直接提升整個(gè)列表等價(jià)。這是traverse恒等律traverse(unit)保持結(jié)構(gòu)的實(shí)證也從側(cè)面驗(yàn)證了Traverse[List]實(shí)例的行為正確性。8.2 快速上手在 Scala REPL / 測(cè)試中試用given實(shí)例定義在Traverse伴生對(duì)象中answers/applicative/Traverse.scalaScala 3 會(huì)自動(dòng)解析。例如把Option當(dāng)作效應(yīng)遍歷Listimport fpinscala.answers.applicative.Traverse.given // List 的 Traverse 在 Option 效應(yīng)中全有則 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效應(yīng)遍歷可以累積所有錯(cuò)誤用State效應(yīng)遍歷可以實(shí)現(xiàn)zipWithIndex等帶狀態(tài)的操作——這些都能在 answers/applicative/Applicative.scala 中找到現(xiàn)成的Applicative實(shí)例optionMonad、validatedApplicative、stateMonad等直接配合使用。九、小結(jié)第 13 題表面上是寫(xiě)四個(gè)given實(shí)則是練習(xí)類型驅(qū)動(dòng)的推導(dǎo)容器核心手法關(guān)鍵要點(diǎn)List[A]foldRightmap2_ :: _自右向左保持元素順序Option[A]模式匹配兩個(gè)分支Some走mapNone走unitTree[A]遞歸 復(fù)用List的遍歷map2重組頭與子樹(shù)Map[K, A]foldLeftmap2m (k - b)逐鍵累積只遍歷值而 hint 中的 Follow the types 不是空話以上四個(gè)實(shí)現(xiàn)中每一步操作的類型都嚴(yán)格收斂幾乎不存在第二種能通過(guò)類型檢查的方案。掌握了這套推導(dǎo)再結(jié)合 answers/applicative/Traverse.scala 中Id、Const、State等特化技巧你就能為任何形狀的數(shù)據(jù)結(jié)構(gòu)寫(xiě)出既正確又優(yōu)雅的Traverse實(shí)例并把map、fold、zip、reverse等能力一次性地全部解鎖。贊分享示例工程【免費(fèi)下載鏈接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala項(xiàng)目地址https://gitcode.com/gh_mirrors/fp/fpinscala點(diǎn)擊查看免費(fèi)下載相關(guān)推薦fpinscala 第 6 章 Applicative 練習(xí) 6用 Monoid 為 Validated 實(shí)現(xiàn)錯(cuò)誤累積的 Applicative 實(shí)例fpinscala 第 6 章 Applicative 練習(xí) 6用 Monoid 為 Validated 實(shí)現(xiàn)錯(cuò)誤累積的 Applicative 實(shí)例 本文圍示例工程fpinscala 精講用 Applicative 的 traverse/sequence 實(shí)現(xiàn)列表轉(zhuǎn)置第 12 章練習(xí) 04fpinscala 精講用 Applicative 的 traverse/sequence 實(shí)現(xiàn)列表轉(zhuǎn)置第 12 章練習(xí) 04 導(dǎo)讀 本篇文章圍繞 fpi示例工程fpinscala 練習(xí) 12.8 詳解用 Applicative.product 組合兩個(gè) Applicative 實(shí)例fpinscala 練習(xí) 12.8 詳解用 Applicative.product 組合兩個(gè) Applicative 實(shí)例 本篇技術(shù)指南聚焦《Function示例工程上一篇終極Tortoise ORM單元測(cè)試指南異步測(cè)試框架集成完整教程下一篇如何快速搭建Enatega外賣系統(tǒng)本地運(yùn)行顧客App、騎手App與管理面板的完整教程創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考