示例工程【免費下載鏈接】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 章節(jié)第 13 題完整講解如何為List、Option、Tree、Map[K, _]四種類型實現(xiàn)Traverse實例。題目給出的提示是跟隨類型走Follow the types我們將從traverse的簽名出發(fā)逐步推導出每種結構唯一合理的實現(xiàn)并對照倉庫中的參考答案與源碼說明這些實例如何與map、foldMap、sequence、mapAccum等操作互相打通。讀完本文你將掌握類型驅動實現(xiàn)的方法論并能獨立為自定義容器類型寫出正確的Traverse實例。一、題目定位13 題在 Traverse 練習線中的位置1.1 練習與參考答案的對應關系倉庫將練習與答案分開存放練習文件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)關鍵點Traverse[F]同時繼承Functor[F]與Foldable[F]即一個可遍歷容器天然既是函子又是可折疊結構traverse接受一個把元素A送入效應上下文G的函數(shù)f: A G[B]并把整個結構F[A]翻轉成G[F[B]]——容器與效應發(fā)生了位置互換默認實現(xiàn)里traverse用map sequence表達sequence又用traverse表達。因此一個具體的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 類型驅動的推導traverse要求返回G[List[B]]而輸入是List[A]。對列表來說最自然的折疊工具是foldRight。我們需要初始值空列表對應的效應值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中元素的相對順序與原始列表一致——這正是保持結構的體現(xiàn)。2.3 一個觀察traverse與Applicative.traverse的關系注意 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)(_ :: _))二者結構完全一致。區(qū)別在于Applicative.traverse是給定一個Applicative[F]遍歷List而Traverse[List]的traverse是List這個容器自己支持在任意Applicative[G]中遍歷。當G取某個具體類型如Option、State、Validated時同樣的foldRight map2模式會反復出現(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等效應這個行為天然表達了短路或成功/失敗的語義。四、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即頭元素 子樹列表。因此遍歷一棵樹需要兩步對頭元素調(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的遍歷時我們直接復用了List的遍歷能力。外層表達式ta.tail.traverse(...)調(diào)用的是List的Traverse實例通過上下文提供的given自動解析而內(nèi)層a.traverse(f)遞歸調(diào)用的是當前Tree實例自身。注意這里的given treeTraverse使用了 new:的寫法而不是with——因為Traverse[Tree]的Traverse特質(zhì)帶有self 自引用別名trait Traverse[F[_]] extends Functor[F], Foldable[F]: self 匿名類實例化時必須用new:語法。這是 Scala 3 中帶自類型別名特質(zhì)的標準實例化方式練習文件中同樣保留了這一寫法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 細節(jié)剖析Map與List不同它沒有天然的頭部插入方向因此這里選用foldLeft從空 Map 出發(fā)逐個鍵累積初始值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, _]]實例帶類型參數(shù)K且容器參數(shù)寫為Map[K, _]即固定鍵類型、任意值類型的容器。這與Foldable、Functor對Map的處理思路一致——鍵是結構的骨架遍歷只作用于值。與sequenceMap的呼應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翻轉的是值已經(jīng)是效應的 MapmapTraverse翻轉的是值經(jīng)過f進入效應的 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同理空列表對應unit(List[B]())非空列表的元素要逐個經(jīng)過f且最終要保持順序這要求f(a)與已遍歷部分用map2組合——foldRight保證順序_ :: _保證拼接。這類推導在整條練習線中反復出現(xiàn)例如 answerkey/applicative/14.answer.md 用Id作為最簡Applicative把traverse退化成mapanswerkey/applicative/15.answer.md 討論Iteration為何是可折疊但不可映射因為它無法從內(nèi)部重建結構answerkey/applicative/16.answer.md 與 answerkey/applicative/17.answer.md 又用mapAccum實現(xiàn)reverse與foldLeft?？梢哉f第 13 題是整條類型驅動實現(xiàn)訓練線的樞紐。七、打通一個traverse實例如何帶出整套操作7.1map與foldMap都是特化因為Traverse[F]繼承Functor[F]與Foldable[F]且只強制實現(xiàn)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已由抽象類給出默認實現(xiàn)toList、zipWithIndex、reverse、zip等則建立在mapAccum內(nèi)部用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]對內(nèi)層結構做遍歷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ù)列表結果應與直接提升整個列表等價。這是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效應遍歷可以實現(xiàn)zipWithIndex等帶狀態(tài)的操作——這些都能在 answers/applicative/Applicative.scala 中找到現(xiàn)成的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 不是空話以上四個實現(xiàn)中每一步操作的類型都嚴格收斂幾乎不存在第二種能通過類型檢查的方案。掌握了這套推導再結合 answers/applicative/Traverse.scala 中Id、Const、State等特化技巧你就能為任何形狀的數(shù)據(jù)結構寫出既正確又優(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點擊查看免費下載相關推薦fpinscala 第 6 章 Applicative 練習 6用 Monoid 為 Validated 實現(xiàn)錯誤累積的 Applicative 實例fpinscala 第 6 章 Applicative 練習 6用 Monoid 為 Validated 實現(xiàn)錯誤累積的 Applicative 實例 本文圍示例工程fpinscala 精講用 Applicative 的 traverse/sequence 實現(xiàn)列表轉置第 12 章練習 04fpinscala 精講用 Applicative 的 traverse/sequence 實現(xiàn)列表轉置第 12 章練習 04 導讀 本篇文章圍繞 fpi示例工程fpinscala 練習 12.8 詳解用 Applicative.product 組合兩個 Applicative 實例fpinscala 練習 12.8 詳解用 Applicative.product 組合兩個 Applicative 實例 本篇技術指南聚焦《Function示例工程上一篇終極Tortoise ORM單元測試指南異步測試框架集成完整教程下一篇如何快速搭建Enatega外賣系統(tǒng)本地運行顧客App、騎手App與管理面板的完整教程創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考