Scala集合的构建——基于集合的数学定义
在过程式编程语言中，我们一般用某种collection来定义集合，集合中元素的数量越多，collection就会占用越大的内存空间，如果集合元素无限多，那么collection就要占用无限大的内存空间，那么在实际的计算机上就不可行了。
为了让集合的构建更加灵活，我们需要从集合的数学定义出发来进行实现。对于一个集合S={x|p(x)}，表示如果对于x，p(x)条件为真，x就是集合S的元素。所以，集合的本质就是定义了元素x和集合关系的函数p(x)，p(x)接受某种类型的参数x，返回Boolean。
1 | type Set = Int => Boolean |
这是Scala的类型定义，含义是定义一个新类型Set，等价于接受一个Int类型参数，返回Boolean的函数。
我们再定义一个函数判断x是不是集合s的元素。
1 | def contains(s: Set, elem: Int): Boolean = s(elem) |
我们现在就可以尝试定义一个集合。
1 2 3 | def odd: Set = {_ % 2 != 0}def r1 = contains(odd, 1) // truedef r2 = contains(odd, 2) // false |
这里odd就是所有奇数的集合。
然后让我们看看如何构建另一种基本的集合，只包含一个元素的集合。
1 2 3 4 | def singletonSet(elem: Int): Set = {_ == elem}def s: Set = singletonSet(100)def r1 = contains(s, 100) // truedef r2 = contains(s, 101) // false |
在定义s的时候使用的elem，被用于将来的比较，这样，我们通过比较传入s的参数和保存下来的elem，就可以知道传入s的参数是不是集合s的元素。
上面这些是集合的基本的building blocks，接下来让我们来定义交、并、差等集合运算，让集合产生新的集合。由于函数式编程的高阶函数特性，构建这种方法非常简单。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 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)} |
上述函数定义完全遵循数学上集合的运算规则。
1 2 3 | def leap: Set = union(diff({_ % 4 == 0}, {_ % 100 == 0}), {_ % 400 == 0})def r1 = contains(leap, 2000) // truedef r2 = contains(leap, 2100) // false |
上面是所有闰年的集合定义，简单组合一下上面的方法就可以构建了。
