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 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(以及其他许多编程语言)中,函数也是对象,可以使用、定义其他对象的地方,也可以使用、定义函数。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相同的协变与逆变规则。
求所有质数——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})})