纯函数式状态（1）

想让状态更新恢复引用透明的关键是让状态更新是显示的。不要以副作用方式更新状态，而是连同生成值一起返回一个新的状态。
纯函数式随机数生成器：

trait RNG {

  def nextInt: (Int, RNG)
}

case class SimpleRNG(seed: Long) extends RNG {
  override def nextInt: (Int, RNG) = {
    val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
    val newRNG = SimpleRNG(newSeed)
    val n = (newSeed >>> 16).toInt
    (n, newRNG)
  }
}

练习 6.1
写一个函数使用RNG.nextInt生成0和Int.MaxValue之间（含）的随机数。

  def nonNegativeInt(rng: RNG): (Int, RNG) = {
    val (v, rng1) = rng.nextInt
    if (v == Int.MaxValue) (0, rng1)
    else (Math.abs(v), rng1)
  }

练习 6.2
写一个函数生成0到1之间的Double数。

  def double(rng: RNG): (Double, RNG) = {
    val (i, rng1) = nonNegativeInt(rng)
    if (i == Int.MaxValue) (0.0, rng1)
    else (i.toDouble / Int.MaxValue, rng1)
  }

练习 6.3
写一个函数生成一个(Int, Double)对，一个(Double, Int)对和一个(Double, Double, Double)三元组。

  def intDouble(rng: RNG): ((Int, Double), RNG) = {
    val (i1, rng1) = rng.nextInt
    val (i2, rng2) = rng1.nextInt
    ((i1, i2.toDouble), rng2)
  }
  
  def doubleInt(rng: RNG): ((Double, Int), RNG) = {
    val ((i, d), rng1) = intDouble(rng)
    ((d, i), rng1)
  }
  
  def double3(rng: RNG): ((Double, Double, Double), RNG) = {
    val ((_, d1), rng1) = intDouble(rng)
    val ((_, d2), rng2) = intDouble(rng1)
    val ((_, d3), rng3) = intDouble(rng2)
    ((d1, d2, d3), rng3)
  }

练习 6.4
写一个函数生成一组随机数。

  def ints(count: Int)(rng: RNG): (List[Int], RNG) = {
    def loop(count: Int, res: (List[Int], RNG)): (List[Int], RNG) = count match {
      case 0 => res
      case _ =>
        val (li, rng) = res
        val (i, rng1) = rng.nextInt
        loop(count - 1, (i :: li, rng1))
    }
    loop(count, (Nil, rng))
  }

状态行为更好的API
回顾我们上述练习的实现，会注意到一个通用的模式：我们每个函数都有一个形式为RNG => (A, RNG)的类型。这种类型的函数被称为状态行为（state action）或状态转移。状态行为可以通过组合子来组合，组合子是一个高阶函数。既然需要一只乏味地重复传递状态参数，何不用组合子帮我们在行为之间自动传递。为了便于学习讨论，我们对RNG状态行为数据类型定义一个类型别名：

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

  val int: Rand[Int] = _.nextInt

  def unit[A](a: A): Rand[A] =
    rng => (a, rng)

  def map[A, B](s: Rand[A])(f: A => B): Rand[B] =
    rng => {
      val (a, rng1) = s(rng)
      (f(a), rng1)
    }
  
  def nonNegativeEven: Rand[Int] =
    map(nonNegativeInt)(i => i - i % 2)

练习 6.5
使用map以更为优雅的方式重新实现double函数，参见练习6.2。

  def double1(rng: RNG): (Double, RNG) =
    map(nonNegativeInt){i =>
      if (i == Int.MaxValue) 0.0 else i.toDouble / Int.MaxValue
    }(rng)

组合状态行为
练习 6.6
按照下面的函数签名写一个map2函数。这个函数接受两个行为，ra和rb，以及一个函数f用于组合它们的结果，并返回一个组合了两者的新行为。

  def map2[A, B, C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] =
    rng => {
      val (a, rng1) = ra(rng)
      val (b, rng2) = rb(rng1)
      (f(a, b), rng2)
    }

练习 利用map2组合子重新实现intDouble和doubleInt函数

  def both[A, B](ra: Rand[A], rb: Rand[B]): Rand[(A, B)] =
    map2(ra, rb)((_, _))
  
  val int: Rand[Int] = _.nextInt

  val doubles: Rand[Double] =
    rng => {
      val (i, rng1) = rng.nextInt
      (i.toDouble, rng1)
    }  

  def intDouble1(rng: RNG): ((Int, Double), RNG) =
    both(int, doubles)(rng)

  def doubleInt1(rng: RNG): ((Double, Int), RNG) =
    both(doubles, int)(rng)

练习 6.7
如果你能组合两个RNG转换行为，那么同样也可以组合一个行为列表。实现sequence函数将一个转换行为列表组合成一个转换行为。使用它实现之前写过的ints函数。

  def sequence[A](fs: List[Rand[A]]): Rand[List[A]] =
    rng => {
      def loop(n: Int, res: (List[A], RNG)): (List[A], RNG) = n match {
        case m if m < 0 => res
        case _ => 
          val (li, rng) = res
          val (a, rng2) = fs(n)(rng)
          loop(n - 1, (a :: li, rng))
      }
      loop(fs.length - 1, (Nil, rng))
    }

  def ints1(count: Int)(rng: RNG): (List[Int], RNG) =
    sequence(List.fill(count)(int))(rng)

嵌套状态行为
map和map2组合子允许我们以特别简洁优雅的方式实现，其它实现方式则显得乏味且容易产生错误，但是所有的函数都可以使用map和map2组合子实现，有时候我们需要连续传递RNG，这时最好的方式使用一个新的组合子帮我们传递，所以我们需要一个更强大的组合子flatMap。
练习 6.8
实现flatMap然后用它实现nonNegativeLessThan。

  def flatMap[A, B](ra: Rand[A])(f: A => Rand[B]): Rand[B] =
    rng => {
      val (a, rng1) = ra(rng1)
      f(a)(rng1)
    }

练习 6.9
根据flatMap重新实现map, map2。这也是flatMap比map和map2更强大的地方。

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

  def map2[A, B, C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] =
    flatMap(ra){a =>
      map(rb){b =>
        f(a, b)
      }
    }