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来进行操作,后面我们会看到具体的实例)。
1 2 3 4 5 6 7 8 9 10 11 12 13 | 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了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 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为空。
1 2 3 4 5 6 7 8 9 10 11 | 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]。
再看一个随机二叉树的例子,思路与列表很类似:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | 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]]。
1 2 3 4 5 6 7 8 9 10 11 | 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]。我们可以像下面这样使用它:
1 2 | 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进行求值,因此我们不担心定义无穷序列会耗尽系统资源,因为只有当取用时才会真正进行求值。
1 2 3 4 | 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的第一个元素的完整过程:
1 2 3 4 5 | primes.head -> sieve(from( 2 )).head -> (from( 2 ).head #:: sieve(from( 2 ).tail filter ( _ % from( 2 ).head ! = 0 ))).head -> from( 2 ).head -> 2 |
可以看到,第三行的#::后面的部分,并不需要进行求值,会等到需要的时候,再进行求值。
让我们再模拟一下取下一个元素的过程,简化的推导过程用->> 表示:
1 2 3 4 5 6 7 | 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的逻辑定义:
1 | 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是质数)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | // 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 })}) |