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中将只有这四种字符串。