1.4 Functional Random Generators

随机数生成是一个很有用的功能，使用 java.util.Random 可以很容易生成 Int 类型的随机数，如果想为任意类型生成随机值应该怎么做呢？在 Scala 中，可以定义一个生成随机值的特质，通过使用 类型参数，使其对所有类型均有效：

trait Generator[+A] {
  def generate: A
}

如果要生成随机整数，则可以定义 Generator[Int] 如下：

val integers: Generator[Int] =
  new Generator[Int] {
    import java.util.Random
    val r = new Random()
    override def generate: Int = r.nextInt()
  }

借助 integers 可以生成随机布尔值：

val booleans: Generator[Boolean] =
  new Generator[Boolean] {
    override def generate: Boolean = integers.generate > 0
  }

也可以生成 (Int, Int) 随机值：

val pairs: Generator[(Int, Int)] =
  new Generator[(Int, Int)] {
    override def generate: (Int, Int) = (integers.generate, integers.generate)
  }

按照上面例子中的方法，可以为很多很多类型生成随机值，但若对于每个类型 T 都需要定义一个 Generator[T] 也未免太啰嗦了，实际上，如下这种生成方式可能更让人开心：

val booleans = for (x <- integers) yield x > 0

def pairs[T, U](t: Generator[T], u: Generator[U]) = for {
  x <- t
  y <- u
} yield (x, y)

可目前 Generator 特质的定义并不支持上面的写法。我们分析一下，Scala 的 for 解析会被编译器“翻译”为 flatMap 和 map 等的组合，所以上面例子实际上会被翻译为：

val booleans = integers map (x => x > 0)

def pairs[T, U](t: Generator[T], u: Generator[U]) =
  t flatMap (x => u map (y => (x, y)))

由此可见，如果 Generator 特质支持 map 和 flatMap 函数，一切就完美了！所以，我们为 Generator 特质添加 map 和 flatMap 函数：

trait Generator[+A] { self ⇒
  def generate: A

  def map[B](f: A ⇒ B): Generator[B] =
    new Generator[B] {
      override def generate: B = f(self.generate)
    }

  def flatMap[B](f: A ⇒ Generator[B]): Generator[B] =
    new Generator[B] {
      override def generate: B = f(self.generate).generate
    }
}

注意 self 的使用

除 map 和 flatMap 之外，下面的组合子会给 Generator 带来很多方便：

object Generator {

  /**
    * unit
    */
  def single[A](x: A): Generator[A] =
    new Generator[A] {
      override def generate: A = x
    }

  /**
    * 返回 [lo, hi) 之间的随机整数
    */
  def choose(lo: Int, hi: Int): Generator[Int] =
    for (x ← integers) yield lo + x % (hi - lo)

  /**
    * 返回变长参数 xs 中的任意一个
    */
  def onOf[A](xs: A*): Generator[A] =
    for (i ← choose(0, xs.length)) yield xs(i)
}

借助这些函数，可以更复杂的类型生成随机值，例如 Generator[List[Int]]：

def lists: Generator[List[Int]] =
  for {
    isEmpty ← booleans
    list ← if (isEmpty) emptyList else nonEmptyList
  } yield list

Generator[List[Int]] 要么生成空列表，要么生成非空列表，其中 emptyList 定义非常直接，使用 single 函数封装 Nil 即可：

val emptyList: Generator[List[Int]] = single(Nil)

而 nonEmptyList 稍微服务，是需要递归调用 lists：

val nonEmptyList: Generator[List[Int]] =
  for {
    hd ← integers
    tl ← lists
  } yield hd :: tl

假设有如下定义：

trait Tree
case class Inner(left: Tree, right: Tree) extends Tree
case class Leaf(value: Int) extends Tree

参考 Generator[List[Int]] 可以很容易实现 Generator[Tree]：

def trees: Generator[Tree] =
  for {
    isLeaf ← booleans
    tree ← if (isLeaf) leaf else inner
  } yield tree

def leaf: Generator[Tree] =
  for {
    v ← integers
  } yield Leaf(v)

def inner: Generator[Tree] =
  for {
    //  递归调用 trees
    l ← trees
    r ← trees
  } yield Inner(l, r)

我们知道，一般的单元测试需要指定输入，然后判断被测函数输出是否符合预期，这样做即使测试通过，也只能保证对于目前给定的输入没有问题。基于性质的测试给出了另外一种思路，不再需要用户指定输入，而是由测试框架自动生成，类似我们这里定义的 Generator，随机生成指定类型的值，例如：

// 基于性质的测试
def test[A](g: Generator[A], times: Int = 100)(p: A ⇒ Boolean): Unit = {
  for (i ← 1 until times) {
    val v = g.generate
    assert(p(v), s"test failed for value: $v")
  }
  println(s"passed $times tests")
}

test 是一个非常简单的基于性质的测试框架，借助 test 可以测试给定规则是否成立：

test(pairs(lists, lists)) {
  case (xs, ys) => (xs ++ ys).length > xs.length
}

借助基于性质的测试框架，我们不再写单元测试，而是将预期保持的性质写下来，这是一种思路的转变。

ScalaCheck 即为 Scala 世界中基于性质的测试框架，既可以单独使用，可以作为 ScalaTest 的组成部分使用。

kun-song / Functional-Programming-in-Scala-Specialization

1.4 Functional Random Generators #5