Deltamaster Tech Center

在过程式编程语言中，我们一般用某种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

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