Coursera 作业之函数集合

本文源码：
https://github.com/wafer-li/scala-coursera/tree/master/funsets

1. 背景知识

该作业是实现一个函数集合的相关内容。

何为函数集合？

一般来说，编程语言中的集合(Collection)都是有限集合；

但是，在数学上，还有很多的集合是无限集合，比如说 负数集；

我们有没有一种办法去表示这个集合呢？

当然有的，对于上面的负数集来说，我们如何知道一个数字是不是负数集中的元素呢？

将它与 0 进行比较，如果 x < 0，那么它就是负数集的元素。

此时，(x) => x == 0 就成为了负数集的判断标准，我们将其作为负数集的 特征函数，通过特征函数来指代特定的集合。

于是，我们得到了函数集合的定义：type Set = (Int) => Boolean

和它的一个基本方法 contains()：

def contains(set: Set, x : Int) = set(x)

2. 基本方法

接下来，题目要求我们实现一些集合的基本方法。

2.1 singletonSet()

如何返回一个只有一个元素的函数集合呢？

对于我们的特征函数来说，也就是只有给定的元素才能满足这个特征函数，这样的集合就是只存在给定元素的集合。

所以，定义如下：

def singletonSet(elem: Int): Set = (x) => x == elem

2.2 交、并、补

这几个基本的数学集合操作并不难，只需要抓住我们特征函数就是 contains() 这一点就行了。

2.3 filter()

这个方法算是在 JVM 函数式语言中经常出现的集合方法；

作用就是返回满足条件的集合内的元素；

其中，一个很有趣的地方在于，filter(s, p) 的两个参数，虽然其表面上的类型不一样；

但是实际上他们的类型是一样的，也就是说，s 和 p 都是集合！

所以，我们只需要返回 s 和 p 的交集就行了

def filter(s: Set, p: Int => Boolean) = intersect(s, p)

3. forAll()

然后，有趣的地方来了，题目要求我们实现一个 forAll() 方法，用来检测是否 所有的 元素都满足给定的条件。

当然，我们不能遍历全部的无限集元素；

所以，我们就采取一个区间的办法，如果在这个区间内的所有的元素都满足条件，那么我们有信心认为所有的元素都满足了条件。

在这里，同样要注意， s 和 p 的类型实际上是一样的！

def forall(s: Set, p: Int => Boolean): Boolean = {
  def iter(a: Int): Boolean = {
    if (a > bound) true
    else if (diff(s, p)(a)) false
    else iter(a + 1)
  }

  iter(-bound)
}

4. exists()

本题第二难的地方来了，题目要求实现一个 exists() 函数，用于检测 是否存在 一个元素满足给定的条件。

按说这个还不是很难，但是，题目要求使用 forAll() 进行实现。

按照我的早就丢给高中老师的逻辑关系知识，『所有』和 『存在』好像并无什么联系。

不过，在论坛上有人提醒了我，可以使用 间接法；

也就是说，我们可以考虑一下 不存在 的情况；

也就是说，对于 所有的 元素，都 不满足 给定的条件；

到此，我们就可以利用上之前实现的 forAll() 了。

def exists(s: Set, p: Int => Boolean) =
    !forAll(s, (elem) => !p(elem))

但是，这显得太长了，能不能缩短到只有一行代码呢？

之前提到，s 和 p 的类型实际上是一样的，也就是说，我们可以重用上面的方法来对 s 和 p 进行处理。

那么，s 和 p 在不存在的情况下，是什么样的关系呢？

我们可以从上面的结论出发继续思考：

对于所有的元素，都不满足给定条件 $\Rightarrow$ 对于 s 的所有元素，都位于「在 s 且不在 p 中」这个集合内

所以，我们得到了一个简便的写法：

def exists(s: Set, p: Int => Boolean) = !forAll(s, diff(s, p))

5. map()

本题最难的部分来了，map() 函数，用于对集合中的元素进行变换操作，返回一个变换过后的新集合。

鉴于我们的集合是一个 函数，那么 map() 方法也就是返回一个 新函数，用来检测参数是否满足新变换过后的条件。

因为 map() 函数是针对原有集合进行变换，所以，我们应该基于原有集合生成上面的新函数。

也就是说，对于原有集合来说，是否存在一个元素，它变换过后的数值和传入的参数相等：

def map(s: Set, f: Int => Int) =
    x => exists(s, elem => x==f(elem))