純粹的 functional 狀態 (1)

這 2 天會使用 隨機數字產生器 來介紹 functional programming 如何操作狀態變更,我們就能學會如何讓那些有狀態的程式純粹化,進而符合 Referential Transparency。

使用 side effect 來產生隨機數

在 Scala 的標準庫中,有個 scala.util.Random 可以用來產生隨機數,

目前電腦上還沒有真正意義上的隨機,都是 Pseudo-Random,有興趣的話看看這篇 介紹 吧。

此 class 十足的依賴 side effect 來產生隨機數,例如下述程式片段(使用 Scala REPL),

scala> import scala.util.Random

scala> val rng = Random
val rng: scala.util.Random.type = scala.util.Random$@62e73ab6

scala> rng.nextDouble
val res0: Double = 0.17978255826607414

scala> rng.nextDouble
val res1: Double = 0.39977332524008824

scala> rng.nextInt
val res2: Int = -798663927

scala> rng.nextInt(10)
val res3: Int = 4

我們可以合理的假設 Random 裡面一定有改變某些值,如此才能讓每一次 nextInt() 的呼叫都能得到不同的結果,代表了每一次的 nextDouble 或 nextInt 調用都有改變 Random 類別裡的成員變數,所以我們可以說這些 function 有 side effect,也就不符合 Referential Transparency,也就難以測試;

假設我們有個 function 會用到隨機數,例如擲骰子好了,

def rollDie: Int =
  val rng = scala.util.Random
  rng.nextInt(5)

rng.nextInt(5) 會回傳 0 ~ 4 的隨機數,但可能當下工程師不知道這件事,所以我們會有測試程式來測試我們寫的 function 邏輯,但此時會有 1/5 的機率測試會失敗,如果失敗,通常我們會重現該錯誤,然後在測試案例中加入該錯誤,來確認我們的 function 是不是能避免該錯誤,但這裡我們無法簡單的覆現 rollDie 回傳 0 這個數字。

pure (純粹) 的隨機數產生器

要讓 nextInt function 符合 RT 的關鍵點就是讓狀態改變明確化,也就是不偷偷摸摸的用 side effect 方式改狀態,直接將新的狀態跟著原來要回傳的值綁在一起返回,以下是新隨機數產生器的介面定義,

trait RNG:
  def nextInt: (Int, RNG)

Scala 的 trait 可把它當作 Java 的 Interface,但比 Interface 更強大,例如 Scala 3 的 trait 就支援宣告成員變數,想了解更多的話可看此文件

nextInt 除了回傳隨機數之外,我們也把改變 seed 狀態之後的隨機數產生器一併回傳,這裡不需要維護 global 範圍的變數值,舊產生器的狀態不會被影響,此狀態還是被封裝在物件中,調用者依舊不需要關心隨機數產生器的實現細節,

以下我們用一個跟 scala.util.Random 相同實作的簡單算法 Linear congruential generator 來實現 RNG,

case class SimpleRNG(seed: Long) extends RNG:
  def nextInt: (Int, RNG) =
    val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL // `&` 是 AND 操作,我們用目前的 seed 來產生新的 seed 
    val nextRNG = SimpleRNG(newSeed) // 下一個 seed 狀態的 RNG
    val n = (newSeed >>> 16).toInt // `>>>` 右移位元運算,然後補 0,`n` 值是我們的 偽隨機數 (pseudo-random)
    (n, nextRNG) // 回傳隨機數以及新 seed 狀態的 RNG

現在我們不管怎麼呼叫 nextInt 都會得到一樣的值了,換句話說我們的 function 變純了。

scala> val rng = SimpleRNG(73)
val rng: SimpleRNG = SimpleRNG(73)

scala> val (n1, rng2) = rng.nextInt
val n1: Int = 28086669
val rng2: RNG = SimpleRNG(1840687985952)

scala> val (n2, rng3) = rng2.nextInt
val n2: Int = 1553204112
val rng3: RNG = SimpleRNG(101790784741035)

scala> rng.nextInt
val res11: (Int, RNG) = (28086669,SimpleRNG(1840687985952))

Exercise D13-1

用 RNG.nextInt 來產生非負的隨機數,範圍介於 0 <= r <= Int.maxValue

def nonNegativeInt(rng: RNG): (Int, RNG)

Exercise D13-2

實現產生浮點數的 function,範圍介於 0 <= r < 1

def double(rng: RNG): (Double, RNG)

Exercise D13-3

實現回傳 (Int, Double)(Double, Int) 隨機數的 function,你需用已實作過的 function 來實現。

  def intDouble(rng: RNG): ((Int, Double), RNG) =
    val (i, rng2) = rng.nextInt
    val (d, rng3) = double(rng2)
    ((i, d), rng3)

  def doubleInt(rng: RNG): ((Double, Int), RNG) =
    val ((i, d), newRng) = intDouble(rng)
    ((d, i), newRng)

更好的 RNG 型態表達方式

有沒有注意到,上面 3 個練習都是以 RNG => (A, RNG) 的模式在定義,泛型 A 可能是 Int 或 Double,這種型態 RNG => (A, RNG) 通常稱為 state transitions,都是從 RNG 轉換到下一個 RNG,

然而在 Scala 中,我們可以用 type Rand[+A] = RNG => (A, RNG) 來為某種型態做別名,這也能讓我們之後的開發簡潔一些,例如以下跟 double 一樣定義的程式,但是是回傳 int。

  def int: Rand[Int] = _.nextInt

現在我們可以使用 Rand 型態,設計能轉變 RNG 結果的 map function,

type Rand[+A] = RNG => (A, RNG)

def map[A, B](s: Rand[A])(f: A => B): Rand[B] =
   rng =>
     val (a, rng2) = s(rng)
     (f(a), rng2)

然後我們就可以用 map function,把產生非負隨機數的 nonNegativeInt function 加工成只產非負偶數 function,

  def nonNegativeEven: Rand[Int] =
    map(nonNegativeInt)(i => i - i % 2)

最後就可以這樣使用。

scala> nonNegativeEven(rng)
val res12: (Int, RNG) = (28086668,SimpleRNG(1840687985952))

Exercise D13-4

用 map 實作 double function。

  def doubleViaMap: Rand[Double]

組合式的 state transitions

Exercise D13-5

跟 map 類似,來試著設計 map2 function,它接收 2 個 Rand 參數,並使用 high-order function 把 A,B 轉變成另一個值。

def map2[A, B, C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C]

有了 map2 後,我們就可以把 intDouble, doubleInt 抽象成 both function 啦!

  def both[A, B](ra: Rand[A], rb: Rand[B]): Rand[(A, B)] =
    map2(ra, rb)((a, b) => (a, b))

  def randIntDouble: Rand[(Int, Double)] =
    both(int, double)

  def randDoubleInt: Rand[(Double, Int)] =
    both(double, int)

Exercise answer


純粹的 functional 狀態 (2)

tshine73
tshine73
文章: 50

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *