更多的練習

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)

巢狀 state transitions

有些情況下，map 和 map2 可能會無法符合組合要求，例如以下這個產生非負數且要小於特定值的隨機數 function，

  def nonNegativeLessThan(n: Int): Rand[Int] =
    map(nonNegativeInt)(_ % n)

這裡有個問題是 Int.maxValue 無法每次都被 n 整除，所以某些數字的出現機率會比較高，所以我們要調整 map 的 high-order function 定義，若發生這種情況我們要 recursive 的再調用 nonNegativeLessThan 一次，但此時我們沒有辦法拿到新狀態的 RNG，

  def nonNegativeLessThan(n: Int): Rand[Int] =
    map(nonNegativeInt) { i =>
      val mod = i % n
      if i + (n - 1) - mod >= 0 then
        mod
      else
        nonNegativeLessThan(n)(???) // 這裡我們沒有新狀態的 rng 給 nonNegativeLessThan 使用
    }

雖然我們可以土法煉鋼的這樣實現，

  def nonNegativeLessThan(n: Int): Rand[Int] =
    rng =>
      val (i, rng1) = nonNegativeInt(rng)
      val mod = i % n
      if i + (n - 1) - mod >= 0 then
        (mod, rng1)
      else
        nonNegativeLessThan(n)(rng1)

但總是不夠優雅，所以此時要請出大神 flatMap function 來救場了，

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

然後我們的 nonNegativeLessThan 就能以 flatMap 的方式實現了，這裡我新加入了名為 unit 的 function，作用為把任意值 a 包裝成 (A, RNG) 後回傳。

  def unit[A](a: A): Rand[A] =
    rng => (a, rng)
    
  def nonNegativeLessThanViaFlatMap(n: Int): Rand[Int] =
    flatMap(nonNegativeInt) {
      i =>
        val mod = i % n
        if i + (n - 1) - mod >= 0 then
          unit(mod)
        else
          nonNegativeLessThan(n)
    }    

因為有了 flatMap，我們可以更進一步的把 map 和 map2 都改成用 flatMap 來實現。

  def mapViaFlatMap[A, B](r: Rand[A])(f: A => B): Rand[B] =
    flatMap(r)(a => unit(f(a)))

  def map2ViaFlatMap[A, B, C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] =
    flatMap(ra)(a => mapViaFlatMap(rb)(b => f(a, b)))

明天繼續！

Day 13 - Exercise answer