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

deltamaster posted @ Jun 20, 2014 08:38:25 PM in Scala with tags Scala 集合 函数 Functional Programming , 1758 阅读

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

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

* 本文在CC BY-SA(署名-相同方式共享)协议下发布。

登录 *


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