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