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

Scala Scala Functional Generator Random 函数式编程 Comments(6) Sep 07, 2014 07:21:21 PM

找零问题——Scala实现

首先简单描述一下这个经典的找零问题：

已知需要找零的数量，以及可用的硬币面值，求用这些面值的硬币，有多少种方法拼凑出要求的找零数量。

比如要求找零4元，可用的硬币只有1元和2元两种面值，那么所有可能的方案是，[1, 1, 1, 1]、[1, 1, 2]、[2, 2]三种。（不同顺序不作为不同方案）

设计一个函数，接受两个参数：

  • money：Int，表示需要拼凑的找零数量。
  • coins：List[Int]，所有可用的硬币面值。

简单分析一下这个问题。直观地用递归的思路去考虑，所有可能的方案，就等于以下两部分之和：

  • 用一枚某种面值的硬币x后，剩余找零数的找零方案数量；
  • 用除了x以外的其他硬币的找零方案数量。

而递归终止条件就是，找零的数量小于或等于0，或者没有硬币可以用了。

  def countChange(money: Int, coins: List[Int]): Int = {
    if (money < 0) 0
    else coins match {
      case Nil => if (money == 0) 1 else 0
      case x::xs => countChange(money - x, coins) + countChange(money, xs)
    }
  }

这段代码用到了Scala的Pattern Matching。Nil是空List对象，继承自List，而x::xs则表示一个非空的List，其中x是用来匹配列表的head，而xs则是列表的tail，xs可以匹配任何List，当然也包括Nil。所以这两个case覆盖了所有的情形，要么为空，要么不为空，如果不为空，则将这个列表decompose成构造参数x和xs，供后面的表达式使用。

Scala scala 递归 找零问题 pattern matching decomposition Comments(6) Jul 06, 2014 12:51:20 PM

Scala集合的构建——基于集合的数学定义

在过程式编程语言中，我们一般用某种collection来定义集合，集合中元素的数量越多，collection就会占用越大的内存空间，如果集合元素无限多，那么collection就要占用无限大的内存空间，那么在实际的计算机上就不可行了。

为了让集合的构建更加灵活，我们需要从集合的数学定义出发来进行实现。对于一个集合S={x|p(x)}，表示如果对于x，p(x)条件为真，x就是集合S的元素。所以，集合的本质就是定义了元素x和集合关系的函数p(x)，p(x)接受某种类型的参数x，返回Boolean。

  type Set = Int => Boolean

这是Scala的类型定义，含义是定义一个新类型Set，等价于接受一个Int类型参数，返回Boolean的函数。

我们再定义一个函数判断x是不是集合s的元素。

  def contains(s: Set, elem: Int): Boolean = s(elem)

我们现在就可以尝试定义一个集合。

  def odd: Set = {_ % 2 != 0}
  def r1 = contains(odd, 1) // true
  def r2 = contains(odd, 2) // false

这里odd就是所有奇数的集合。

然后让我们看看如何构建另一种基本的集合，只包含一个元素的集合。

  def singletonSet(elem: Int): Set = {_ == elem}
  def s: Set = singletonSet(100)
  def r1 = contains(s, 100) // true
  def r2 = contains(s, 101) // false

在定义s的时候使用的elem，被用于将来的比较，这样，我们通过比较传入s的参数和保存下来的elem，就可以知道传入s的参数是不是集合s的元素。

上面这些是集合的基本的building blocks，接下来让我们来定义交、并、差等集合运算，让集合产生新的集合。由于函数式编程的高阶函数特性，构建这种方法非常简单。

  def union(s: Set, t: Set): Set = {
    x: Int => contains(s, x) || contains(t, x)
  }

  def intersect(s: Set, t: Set): Set = {
    x: Int => contains(s, x) && contains(t, x)
  }

  def diff(s: Set, t: Set): Set = {
    x: Int => contains(s, x) && !contains(t, x)
  }

  def filter(s: Set, p: Int => Boolean): Set = {
    x: Int => contains(s, x) && p(x)
  }

上述函数定义完全遵循数学上集合的运算规则。

  def leap: Set = union(diff({_ % 4 == 0}, {_ % 100 == 0}), {_ % 400 == 0})
  def r1 = contains(leap, 2000) // true
  def r2 = contains(leap, 2100) // false

上面是所有闰年的集合定义，简单组合一下上面的方法就可以构建了。

Scala Scala 集合 函数 Functional Programming Comments(6) Jun 20, 2014 08:38:25 PM

Scala List的协变特性——泛型上界与下界

先做一个简化的List定义，List对象由head（第一个元素）和tail（除了第一个元素以外所有后续元素组成的List）组成。Nil是空List对象，由于不论List的泛型类型是什么，空List的含义和行为都没有区别，因此全局只需要存在一个空List对象即Nil。

trait List[+T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
}

class Cons[T](val head: T, val tail: List[T]) extends List[T] {
  def isEmpty = false
}

object Nil extends List[Nothing] {
  def isEmpty: Boolean = true
  def head: Nothing = throw new NoSuchElementException("Nil.head")
  def tail: Nothing = throw new NoSuchElementException("Nil.tail")
}

这样就完成了List的定义。我们可以通过下面的方式来定义List对象了。

  val x: List[String] = Nil
  val ages: List[Int] = new Cons(16, new Cons(22, Nil))

首先让我们注意一下Nil的定义，Nil这个单例对象所属的类，继承自List[Nothing]，为什么可以将List[String]类型的x定义为这个对象？因为泛型类型T是协变的，而Nothing在Scala中是所有其他类的子类。所以List[Nothing]就是List[String]的子类，根据Liskov替换原则，这样的定义是合法的。

下面，我们要像List类增加一个prepend方法，用来生成一个新List，这个新List是在原List头部新增一个元素：

trait List[+T] {
  // omit other methods
  def prepend(elem: T): List[T] = new Cons(elem, this)
}

但是这样的做法是无法通过编译的。为什么？正如上一篇博客所解释的，协变类型不能作为方法的参数类型。而这样的prepend操作看似是非常符合常理的，那么是Scala的这个规则设定不合理吗？

我们再回想一下Liskov替换原则。如果Bird是Animal的子类，那么List[Bird]就是List[Animal]的子类，那么如果List[Animal]可以prepend一个Animal类型的实例，List[Bird]也可以prepend一个Animal类型的实例，可惜按照上面的定义是不可能的，因此违反了Liskov替换原则，这样的定义是错误的。

为了解决这个问题，我们需要引入泛型类型的下界的概念。

trait List[+T] {
  // omit other methods
  def prepend[U >: T](elem: U): List[U] = new Cons(elem, this)
}

这个定义的含义是，prepend方法接受一个类型为U的参数，U必须是T或T的父类（“>:”表示泛型类型的下界，而“<:”则相应地表示上界），返回类型则是List[U]。拿Animal和Bird的例子，再假设Chicken是Bird的子类，那么根据这种定义，List[Bird]可以prepend一个Animal的实例，返回List[Animal]，而prepend一个Chicken的实例并非不允许，而是U类型不会是Chicken，必须将U类型至少提升至Bird，所以prepend一个Chicken的实例，结果是返回List[Bird]。这样的定义满足Liskov替换原则，所有可以对List[Animal]进行的操作，都可以对List[Bird]进行。

接下来再举一个例子，假设BaldEagle和CrownEagle都是Aeroplane的子类，而BaldEagle和CrownEagle没有关系。那么List[BaldEagle]如果prepend一个CrownEagle的实例会是什么结果呢？类型U不能是CrownEagle，而必须被向上提升直到U是BaldEagle或者BaldEagle的父类，因此U将被提升到Aeroplane，所以结果将是返回List[Aeroplane]。

这样，可以容易地推断出Scala对于泛型上下界的规定。

  • 协变类型可以作为泛型类型的下界
  • 逆变类型可以作为泛型类型的上界

Scala scala 函数 泛型 Functional Programming Liskov 协变 逆变 Comments(6) Jun 19, 2014 09:36:57 PM

Scala函数的泛型特性——逆变与协变

在Scala（以及其他许多编程语言）中，函数也是对象，可以使用、定义其他对象的地方，也可以使用、定义函数。Scala中的函数，具有apply方法的类的实例，就可以当做函数来使用。其中apply接受的参数就是函数的参数，而apply的返回值就是函数的返回值。

首先给出一个接受一个参数的函数的泛型定义。

trait Function1[-T, +U] {
  def apply(x: T): U
}

这种函数接受一个参数，参数类型为泛型类型T，返回类型为泛型类型U。和其他支持泛型的语言一样，实际定义函数时T和U的类型会被确定下来，不过需要注意的是，这边的T之前有一个“-”，而U之前有一个“+”。

在这里引入关于这个符号的说明，在声明Scala的泛型类型时，“+”表示协变，而“-”表示逆变。

  • C[+T]：如果A是B的子类，那么C[A]是C[B]的子类。
  • C[-T]：如果A是B的子类，那么C[B]是C[A]的子类。
  • C[T]：无论A和B是什么关系，C[A]和C[B]没有从属关系。

根据Liskov替换原则，如果A是B的子类，那么能适用于B的所有操作，都适用于A。让我们看看这边Function1的定义，是否满足这样的条件。假设Bird是Animal的子类，那么看看下面两个函数之间是什么关系：

def f1(x: Bird): Animal // instance of Function1[Bird, Animal]
def f2(x: Animal): Bird // instance of Function1[Animal, Bird]

在这里f2的类型是f1的类型的子类。为什么？

我们先看一下参数类型，根据Liskov替换原则，f1能够接受的参数，f2也能接受。在这里f1接受的Bird类型，f2显然可以接受，因为Bird对象可以被当做其父类Animal的对象来使用。

再看返回类型，f1的返回值可以被当做Animal的实例使用，f2的返回值可以被当做Bird的实例使用，当然也可以被当做Animal的实例使用。

所以我们说，函数的参数类型是逆变的，而函数的返回类型是协变的。

那么我们在定义Scala类的时候，是不是可以随便指定泛型类型为协变或者逆变呢？答案是否定的。通过上面的例子可以看出，如果将Function1的参数类型定义为协变，或者返回类型定义为逆变，都会违反Liskov替换原则，因此，Scala规定，协变类型只能作为方法的返回类型，而逆变类型只能作为方法的参数类型。类比函数的行为，结合Liskov替换原则，就能发现这样的规定是非常合理的。

这种函数的泛型特性对于函数式编程非常有用。尽管C++的泛型在语法层面上不支持协变与逆变，但在C++11的function<U(T)>中，返回类型U和参数类型T也同样遵循与Scala相同的协变与逆变规则。

Scala scala 函数 泛型 Functional Programming Liskov 协变 逆变 Comments(5) Jun 17, 2014 10:22:10 PM

求所有质数——Eratosthenes筛法的Scala实现及证明

Eratosthenes筛法是以筛选（filter）为基本思想的计算质数的一种数学方法。求解n以内的质数步骤如下：

  1. 创建一个[2, n]的自然数列表
  2. val p=2（p是找到的第一个质数）
  3. for (x = 2; x * p <= n; x++) { 从列表中去掉x*p }
  4. 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})})

 

Scala scala 证明 函数式编程 编程语言 Eratosthenes Functional Programming Comments(10) Jun 16, 2014 09:25:08 PM