Coursera 作业之函数集合

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

1. 背景知识

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

何为函数集合?

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

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

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

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

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

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

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

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

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

2. 基本方法

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

2.1 singletonSet()

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

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

所以,定义如下:

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

2.2 交、并、补

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

2.3 filter()

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

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

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

但是实际上他们的类型是一样的,也就是说,sp 都是集合!

所以,我们只需要返回 sp 的交集就行了

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

3. forAll()

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

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

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

在这里,同样要注意, sp 的类型实际上是一样的!

1
2
3
4
5
6
7
8
9
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() 了。

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

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

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

那么,sp 在不存在的情况下,是什么样的关系呢?

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

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

所以,我们得到了一个简便的写法:

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

5. map()

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

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

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

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

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