示例工程【免費(fèi)下載鏈接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala項目地址https://gitcode.com/gh_mirrors/fp/fpinscala點(diǎn)擊查看免費(fèi)下載本篇技術(shù)指南圍繞 fpinscala 倉庫《Functional Programming in Scala》一書的配套練習(xí)與答案庫第 6 章 state 章節(jié)的練習(xí) 4 展開深入講解如何在純函數(shù)式風(fēng)格下實(shí)現(xiàn)ints給定數(shù)量count與隨機(jī)數(shù)生成器RNG一次性產(chǎn)出一串隨機(jī)Int。通過對照倉庫中的練習(xí)文件、標(biāo)準(zhǔn)答案與屬性測試源碼你將掌握顯式狀態(tài)傳遞state threading這一核心范式理解普通遞歸與尾遞歸兩種寫法的差異、列表構(gòu)造順序的微妙之處并看到它如何被后續(xù)的Rand/sequence抽象所取代。一、練習(xí)背景為什么隨機(jī)數(shù)生成必須手動傳狀態(tài)在進(jìn)入ints之前需要先理解第 6 章確立的純函數(shù)式隨機(jī)數(shù)生成模型。該章的練習(xí)骨架位于 src/main/scala/fpinscala/exercises/state/State.scala其中定義了核心抽象trait RNG: def nextInt: (Int, RNG) // Should generate a random Int.關(guān)鍵點(diǎn)在于nextInt不返回單個整數(shù)而是返回一個二元組(Int, RNG)——既包含生成的偽隨機(jī)整數(shù)又包含下一個隨機(jī)數(shù)生成器狀態(tài)。這樣做的目的是保持純函數(shù)pure function與引用透明性referential transparency同一個RNG實(shí)例調(diào)用nextInt永遠(yuǎn)得到相同結(jié)果不會像java.util.Random那樣悄悄修改內(nèi)部可變狀態(tài)。倉庫中給出的具體實(shí)現(xiàn)是經(jīng)典的線性同余生成器LCG見 src/main/scala/fpinscala/answers/state/State.scalacase class Simple(seed: Long) extends RNG: def nextInt: (Int, RNG) val newSeed (seed * 0x5DEECE66DL 0xBL) 0xFFFFFFFFFFFFL // is bitwise AND. val nextRNG Simple(newSeed) val n (newSeed 16).toInt // is right binary shift with zero fill. (n, nextRNG)由此ints的問題就具體化了想要連續(xù)生成count個隨機(jī)整數(shù)就必須把每一次nextInt返回的新狀態(tài)作為下一次調(diào)用的輸入狀態(tài)像鏈條一樣串聯(lián)下去——這一過程被稱為顯式狀態(tài)傳遞。二、練習(xí) 4 的題目要求與答案原文練習(xí) 4 要求實(shí)現(xiàn)的函數(shù)簽名在練習(xí)文件中以???占位見 src/main/scala/fpinscala/exercises/state/State.scala#L39def ints(count: Int)(rng: RNG): (List[Int], RNG) ???語義是生成一個長度為count的隨機(jī)整數(shù)列表同時返回最終的狀態(tài)RNG供后續(xù)繼續(xù)生成使用。該練習(xí)的 hint 文件 answerkey/state/04.hint.md 中只有一個-表示沒有提供提示需要自行推理——此時答案文件的價值就體現(xiàn)出來了。關(guān)聯(lián)文檔 answerkey/state/04.answer.md 給出了兩種完整解法下面分別展開。三、解法一簡單遞歸——按生成順序逐個構(gòu)造列表答案原文的第一種寫法// A simple recursive solution def ints(count: Int)(rng: RNG): (List[Int], RNG) if count 0 then (List(), rng) else val (x, r1) rng.nextInt val (xs, r2) ints(count - 1)(r1) (x :: xs, r2)逐行拆解基準(zhǔn)情形當(dāng)count 0時不再生成任何數(shù)返回空列表List()并且原樣返回傳入的rng。注意這里用的是 0而不是 0意味著負(fù)數(shù)輸入也安全——這一點(diǎn)與倉庫測試中Gen.choose(-5, 20)的生成范圍見下文測試章節(jié)完全對應(yīng)。遞歸情形val (x, r1) rng.nextInt從當(dāng)前狀態(tài)rng取一個整數(shù)x得到新狀態(tài)r1val (xs, r2) ints(count - 1)(r1)把r1而不是原來的rng傳給遞歸調(diào)用繼續(xù)生成剩余count - 1個整數(shù)得到列表xs與最終狀態(tài)r2(x :: xs, r2)把本次生成的x用 cons 接到xs前面連同最終狀態(tài)r2一起返回。這種寫法的核心是嚴(yán)格串行傳遞狀態(tài)rng → r1 → r2每一次nextInt都消費(fèi)前一次產(chǎn)生的新狀態(tài)從而保證序列不重復(fù)、可復(fù)現(xiàn)。由于先取x、再遞歸生成xs結(jié)果列表中的元素按生成順序排列x1 :: x2 :: x3 :: ...。這份答案在倉庫完整實(shí)現(xiàn)中位于 src/main/scala/fpinscala/answers/state/State.scala#L54-L61與練習(xí)文件中的占位簽名一一對應(yīng)可直接對照閱讀。四、解法二尾遞歸——用累加器換取恒定棧空間答案原文的第二種寫法// A tail-recursive solution def ints2(count: Int)(rng: RNG): (List[Int], RNG) def go(count: Int, r: RNG, xs: List[Int]): (List[Int], RNG) if count 0 then (xs, r) else val (x, r2) r.nextInt go(count - 1, r2, x :: xs) go(count, rng, List())逐行拆解在外部函數(shù)ints2內(nèi)部定義局部輔助函數(shù)go它額外攜帶一個累加器參數(shù)xs: List[Int]用于邊走邊攢已生成的整數(shù)基準(zhǔn)情形count 0時直接把累加器xs與當(dāng)前狀態(tài)r返回遞歸情形取一個整數(shù)x與新狀態(tài)r2后遞歸調(diào)用go自身并把xcons 進(jìn)累加器x :: xs——遞歸調(diào)用是整個函數(shù)體的最后一個動作因此這是真正的尾遞歸tail recursionScala 編譯器可將其優(yōu)化為循環(huán)棧深度恒定不會因count很大而棧溢出。這里有一個值得注意的細(xì)節(jié)累加器版本的列表順序與生成順序相反。以count 3為例執(zhí)行軌跡為取x1go(2, r2, x1 :: Nil)取x2go(1, r3, x2 :: x1 :: Nil)取x3go(0, r4, x3 :: x2 :: x1 :: Nil)→ 返回[x3, x2, x1]。即先取出的數(shù)反而排在列表末尾。這一現(xiàn)象與答案文件在sequence注釋中討論的foldRight/foldLeft順序問題如出一轍見 src/main/scala/fpinscala/answers/state/State.scala#L111-L119若對輸出順序有要求通常的做法是結(jié)束時對累加器做一次reverse。而倉庫的測試只校驗值互不相同不校驗順序因此兩種寫法在測試視角下是等價的。五、兩種解法對比何時選用哪一種維度簡單遞歸ints尾遞歸ints2結(jié)果順序與生成順序一致x1 :: x2 :: ...與生成順序相反累加器 cons 所致?？臻gO(count)隨輸入線性增長O(1)編譯器可優(yōu)化為循環(huán)時間/堆空間O(count)結(jié)果列表本身占 O(count)同左可讀性直接、貼近逐次生成的直覺需理解累加器技巧邊界處理count 0返回空列表與原始rng同左兩條經(jīng)驗法則追求棧安全count可能很大時優(yōu)先尾遞歸版本并可用tailrec注解讓編譯器強(qiáng)制校驗倉庫測試輔助函數(shù)checkRND就使用了import scala.annotation.tailrec見 src/test/scala/fpinscala/exercises/state/RNGSuite.scala#L10追求結(jié)果順序自然時用簡單遞歸或在尾遞歸版本末尾補(bǔ)一次reverse。無論哪種寫法都必須恪守同一原則每輪生成只使用上一輪返回的新RNG狀態(tài)絕不能重復(fù)使用舊狀態(tài)否則會產(chǎn)生重復(fù)序列。六、倉庫測試如何驗證 ints 的正確性練習(xí)的驗證依托屬性測試框架PropSuite針對ints的測試位于 src/test/scala/fpinscala/exercises/state/RNGSuite.scala#L55-L58test(RNG.ints)(genRNG ** genCounter ** genLengthOfList): case rng ** counter ** lengthOfList if lengthOfList 0 then assert(ints(lengthOfList)(rng)._1.isEmpty) else assert(checkRND(rng, counter, ints(lengthOfList), list list list.distinct))它覆蓋了兩個關(guān)鍵性質(zhì)負(fù)數(shù)與零輸入genLengthOfList Gen.choose(-5, 20)見 RNGSuite.scala#L15當(dāng)lengthOfList 0時斷言結(jié)果列表為空——這正是答案中count 0基準(zhǔn)情形要保證的值互不重復(fù)對正數(shù)長度用輔助函數(shù)checkRND連續(xù)跑counter輪斷言list list.distinct即列表內(nèi)沒有重復(fù)元素。由于每次生成都消費(fèi)新狀態(tài)這個性質(zhì)得以成立。在倉庫根目錄README 的構(gòu)建說明見 README.md#L62-L96可以用 Scala CLI 單獨(dú)運(yùn)行該包的所有測試$ scala-cli test . -- fpinscala.exercises.state.*注意倉庫設(shè)計上未完成練習(xí)時測試會失敗stub 為???完成后即可通過。七、延伸從手寫狀態(tài)傳遞到 sequence 抽象ints的手工實(shí)現(xiàn)暴露了一個明顯的痛點(diǎn)每次都不得不在代碼里顯式攜帶rng變量并層層傳遞正如上一題 answerkey/state/03.answer.md 末尾的注釋所感嘆的——There is something terribly repetitive about passing the RNG along every time.每次都把 RNG 傳來傳去實(shí)在太重復(fù)了。答案文件隨后給出了解法先用類型別名抽象出Rand[A] RNG (A, RNG)再定義unit、map、map2最終用foldRight組合出sequence見 src/main/scala/fpinscala/answers/state/State.scala#L120-L128def sequenceA: Rand[List[A]] rs.foldRight(unit(Nil: List[A]))((r, acc) map2(r, acc)(_ :: _)) def _ints(count: Int): Rand[List[Int]] sequence(List.fill(count)(int))可以看到sequence內(nèi)部正是以foldRight復(fù)刻了練習(xí) 4 中手寫遞歸的構(gòu)造邏輯_ :: _逐元素 cons而_ints一行即等價于ints的聲明式版本。答案注釋還點(diǎn)明sequence的實(shí)現(xiàn)從未直接談?wù)摼唧w的RNG類型這是它能夠進(jìn)一步泛化為State[S, A]抽象opaque type見 State.scala#L146的強(qiáng)信號——同樣的foldRightmap2模式在State.sequence中原樣復(fù)用State.scala#L171-L172并最終支撐起糖果機(jī)模擬simulateMachine等更復(fù)雜的應(yīng)用。因此練習(xí) 4 的ints不僅是隨機(jī)數(shù)生成的一個實(shí)用工具更是理解顯式狀態(tài)傳遞 → Rand 組合子 → 通用 State 抽象這條抽象化主線的關(guān)鍵一步。掌握它的遞歸與尾遞歸兩種寫法也就掌握了第 6 章后續(xù)所有內(nèi)容的地基。贊分享示例工程【免費(fèi)下載鏈接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala項目地址https://gitcode.com/gh_mirrors/fp/fpinscala點(diǎn)擊查看免費(fèi)下載相關(guān)推薦fpinscala 練習(xí)精解用 Scala 3 尾遞歸實(shí)現(xiàn)斐波那契數(shù)列第 2 章 Exercise 1fpinscala 練習(xí)精解用 Scala 3 尾遞歸實(shí)現(xiàn)斐波那契數(shù)列第 2 章 Exercise 1 導(dǎo)讀 本文圍繞 fpinscala 倉庫第 2 章示例工程fpinscala 練習(xí)精講用多態(tài)函數(shù)與尾遞歸實(shí)現(xiàn) isSorted 有序性檢測第 2 章練習(xí) 2 詳解fpinscala 練習(xí)精講用多態(tài)函數(shù)與尾遞歸實(shí)現(xiàn) isSorted 有序性檢測第 2 章練習(xí) 2 詳解 本文以 answerkey/gettingsta示例工程fpinscala 第 3 章練習(xí) 23 精解用模式匹配與尾遞歸實(shí)現(xiàn) List 的 zipWithfpinscala 第 3 章練習(xí) 23 精解用模式匹配與尾遞歸實(shí)現(xiàn) List 的 zipWith 本文以 fpinscala 倉庫中 answerkey/d示例工程創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考