Scala随机数生成及复杂Generator的构造
在程序中使用随机数的需求很普遍，有时候我们还需要用到一些更加复杂的随机数据结构，比如生成一个随机的列表或者二叉树等，探索性测试可以算一个典型的应用场景。
在Scala中生成一个随机整数有现成的函数可用：scala.util.Random.nextInt()。让我们看看我们如何基于它来用优雅简洁的程序构造一些更复杂的generator。
我们首先要对Generator的功能进行必要的抽象：
- 首先，Generator[T]需要一个generate方法来随机产生一个T类型的对象；
- 需要一个map方法，给定一个T=>S类型的映射函数f，产生Generator[S]；（可对比List[T]的map(f: T=>S): List[S]方法理解）
- 需要一个flatMap方法，给定一个T=>Generator[S]类型的映射函数f，产生Generator[S]。（可对比List[T]的flatMap(f: T=>List[S]): List[S]方法理解）
通过上面的陈述，可以看到我们将Generator抽象为一种容器，这将给我们以后的扩展带来很大的便利（利用Scala的for来进行操作，后面我们会看到具体的实例）。
trait Generator[+T] {
self => // an alias for "this"
def generate: T
def map[S](f: T => S): Generator[S] = new Generator[S] {
def generate = f(self.generate)
}
def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] {
def generate = f(self.generate).generate
}
}
这就是Generator的抽象定义了，其中self是this的别名，注意下面两处使用“self”的地方，请思考一下为什么不能使用“this”，这里就不详细解释了。
基于这个抽象的定义，我们就可以构造一些基本的Generator了。
def integers = new Generator[Int] {
def generate = scala.util.Random.nextInt()
}
def booleans = integers map (_ >= 0)
def single[T](x: T): Generator[T] = new Generator[T] {
def generate = x
}
def choose(lo: Int, hi: Int): Generator[Int] =
for (x <- integers) yield lo + Math.abs(x) % (hi - lo)
def oneOf[T](xs: T*): Generator[T] =
for (idx <- choose(0, xs.length)) yield xs(idx)
其中：
- integers用于生成随机整数；
- booleans用于生成随机布尔值，这里就使用了map方法，通过Int=>Boolean函数，将类型Generator[Int]映射成了Generator[Boolean]；
- single用于生成特定值；
- choose用于生成位于lo和hi之间的整数（不包含hi）；
- oneOf用于随机取列表中的值，比如oneOf(1, 10, 100, 1000).generate将会随机产生这四个数中的一个。
下面我们要利用这些基本的Generator来构造随机List[Int]，所以我们就需要一个Generator[List[Int]]，生成策略是：
- 首先生成一个随机布尔值，如果为真，则直接返回空列表的Generator，否则返回非空列表的Generator；
- 对于非空列表，head是随机整形，tail是一个随机列表（当然即有可能是空，也可能非空），于是递归这两个步骤直到tail为空。
def intLists: Generator[List[Int]] = for {
isEmpty <- booleans
list <- if (isEmpty) emptyIntLists else nonEmptyIntLists
} yield list
def emptyIntLists = single(Nil)
def nonEmptyIntLists = for {
head <- integers
tail <- intLists
} yield head :: tail
这里就用到了integers、booleans和single三个基本的Generator，同时利用for间接调用map和flatMap方法，产生新的Generator。这样，intLists.generate就会产生一个随机的List[Int]。
再看一个随机二叉树的例子，思路与列表很类似：
trait Tree {
def toStringWithIndent(level: Int): String = this match {
case Leaf(x) => " " * level + x.toString + "\n"
case Inner(l, r) => " " * level + "LNode:\n" + l.toStringWithIndent(level + 1) + " " * level + "RNode:\n" + r.toStringWithIndent(level + 1)
}
override def toString = toStringWithIndent(0)
}
case class Leaf(val x: Int) extends Tree
case class Inner(val l: Tree, val r: Tree) extends Tree
// End of Tree definition
def leafs: Generator[Leaf] = for {
x <- integers
} yield Leaf(x)
def inners: Generator[Inner] = for {
l <- trees
r <- trees
} yield Inner(l, r)
def trees: Generator[Tree] = for {
isLeaf <- booleans
tree <- if (isLeaf) leafs else inners
} yield tree
不难理解，这里就不再详细解释。
再更进一步，对于上面的intLists，我们能否创造一个更加普适的Generator，使得不仅限于产生随机的List[Int]，而是根据给定的Generator[T]，产生List[T]，这意味着我们需要构造一个Generator[List[T]]。
def lists[T](g: Generator[T]): Generator[List[T]] = for {
isEmpty <- booleans
list <- if (isEmpty) emptyLists else nonEmptyLists(g)
} yield list
def emptyLists = single(Nil)
def nonEmptyLists[T](g: Generator[T]) = for {
head <- g
tail <- lists(g)
} yield head :: tail
与上面intLists的不同之处在于，我们将原先使用integers这个Generator的地方，换成了我们指定的g: Generator[T]。我们可以像下面这样使用它：
lists(integers).generate // equivalent to intLists.generate
lists(oneOf("Adam", "Brion", "Chris", "Daniel")).generate
其中第一行与intLists.generate等价，第二行使用了oneOf这个Generator，产生的List中将只有这四种字符串。
求所有质数——Eratosthenes筛法的Scala实现及证明
Eratosthenes筛法是以筛选（filter）为基本思想的计算质数的一种数学方法。求解n以内的质数步骤如下：
- 创建一个[2, n]的自然数列表
- val p=2（p是找到的第一个质数）
- for (x = 2; x * p <= n; x++) { 从列表中去掉x*p }
- p=列表中的下一个数，重复上面一步
当列表中的数遍历完，这个列表就是n以内的所有质数。我们很容易根据上述思路用任何一种语言进行实现。下面我们要利用函数式编程中的延迟求值（lazy evaluation）特性来实现求[2, +Infinity)的所有质数，在这里使用Scala语言中的Stream作为容器。
Stream的功能及操作方法类似与List，但是它的tail部分会在需要tail.head时才对tail.head进行求值，因此我们不担心定义无穷序列会耗尽系统资源，因为只有当取用时才会真正进行求值。
def sieve(s: Stream[Int]): Stream[Int] = s.head #:: sieve(s.tail filter (_ % s.head != 0)) def primes = sieve(from(2))
上面三行就是全部的实现代码了。
其中，sieve就是Eratosthenes筛法中的第三步和第四步的循环，s.head的值就是当前的p，因此留下s.head，在后面所有的元素中，除去能够被p整除的数，使用sieve本身进行筛选。再将s.head prepend到新的tail之前。而from(2)将产生一个从2开始直到正无穷的Stream，作为初始的s，传给sieve方法，就能返回包含所有的质数的Stream。
让我们模拟一下Scala取primes的第一个元素的完整过程：
primes.head
-> sieve(from(2)).head
-> (from(2).head #:: sieve(from(2).tail filter (_ % from(2).head != 0))).head
-> from(2).head
-> 2
可以看到，第三行的#::后面的部分，并不需要进行求值，会等到需要的时候，再进行求值。
让我们再模拟一下取下一个元素的过程，简化的推导过程用->> 表示：
primes.tail.head
-> sieve(from(2)).tail.head
->> (from(2).head #:: sieve(from(2).tail filter (_ % from(2).head != 0))).tail.head
->> sieve(from(2).tail filter (_ % 2 != 0)).head
-> ((from(2).tail filter (_ % 2 != 0)).head #:: sieve((from(2).tail filter (_ % 2 != 0)).tail) filter (_ % (from(2).tail filter (_ % 2 != 0)).head != 0))).head
->> (3 #:: sieve((from(2).tail filter (_ % 2 != 0)).tail) filter (_ % 3 != 0))).head
-> 3
这边filter的语义比较直观，展开又过于繁琐，在这里就进行了简化。
下面我们来简单证明一下这个算法的正确性，即要证明primes中的所有元素都是质数。
首先，我们回顾一下isPrime的逻辑定义：
def isPrime(n: Int) = !((2 to n - 1) exists (n % _ == 0))
首先取s=primes，证明s不包含能被2整除的数（显然）。我们在刚才的模拟过程中已经进行了完整的证明，根据质数的定义，isPrime(2)=true。
然后要证明，如果s中不包含能被从2到s.head-1中的数整除的数（s.head是质数），s中就不包含能被2到s.tail.head-1中的数整除的数（s.tail.head是质数）。
// Condition:
!(s exists {x => !((2 to s.head - 1) exists {y => x % y == 0})})
s.tail.head
->> sieve(s.tail filter (_ % s.head != 0)).head
// Therefore (according to definition of "filter"):
->> !((2 to s.head) exists (s.tail.head % _ == 0)
// Hypothesis
!isPrime(s.tail.head)
-> (2 to s.tail.head - 1) exists (s.tail.head % _ == 0)
-> (s.head + 1 to s.tail.head - 1) exists (s.tail.head % _ == 0)
->> (s.head + 1 to s.tail.head - 1) contains s.tail.head // Impossible, contradiction
isPrime(s.tail.head)
!(s exists {x => !((2 to s.tail.head - 1) exists {y => x % y == 0})})
