Scala随机数生成及复杂Generator的构造

deltamaster posted @ Sep 07, 2014 07:21:21 PM in Scala with tags Scala Functional Generator Random 函数式编程 , 8602 阅读

在程序中使用随机数的需求很普遍,有时候我们还需要用到一些更加复杂的随机数据结构,比如生成一个随机的列表或者二叉树等,探索性测试可以算一个典型的应用场景。

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

* 本文在CC BY-SA(署名-相同方式共享)协议下发布。
housekeeping service 说:
Sep 24, 2021 08:28:52 PM

Maids can assist you to handle some of these tasks. You can easily hire them for just this move-in form of service if which is all you have to. On one other hand, you can easily hire them an extra shot after you might have moved in for long-term, regular care of the property. As any busy specialist, you would not have the time and energy to put into this technique all on your own, but it is possible to still acquire help for your cleanup a lot more quickly than you recognize.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter