Haskell 集合数学 C#

IT中的数学 #1：基本集合论

Sander Rossel

4.95/5 (25投票s)

2015年11月3日

CPOL

9分钟阅读

53605

集合论的简单介绍

在这篇文章中，我为你准备了些不同寻常的内容。没有新的语言或框架，而是要讲一些存在了数千年的东西：数学。

当问及程序员关于数学的问题时，你会发现两种人：一种人说你不需要数学就能成为一名优秀的程序员，另一种人则认为数学是必不可少的。就个人而言，我认为两者都对。对于某些应用和行业，你确实不需要高深的数学知识，但如果你要涉足机器人技术、机器学习、统计学等领域，那么你将需要数学，而且需要很多。无论你是否需要它，计算机、编程语言和数据库的诞生都离不开数学。

现在，让我们这样说吧：了解一两点数学知识，能让你在程序员的道路上更具优势！

数学无处不在：物理、化学、生物、经济，甚至艺术！在这个系列中，我将专注于IT中我们需要的数学。我不知道这个系列会有多少篇文章，也不知道我会讨论什么（或不讨论什么），但我一定会尽量保持其实用性。不需要任何先前的数学知识。别担心，我偶尔还是会发布关于代码的文章的！

集合

我需要告诉你为什么要学习集合吗？你可能每天都在代码中使用它们，例如数组、数据库表、列表或哈希表。你可能不知道的是，集合拥有大量的数学理论！由于集合在数学和编程中都非常重要，我将从这里开始这个系列。更具体地说，我们将讨论集合。

集合是包含唯一不重复值的无序集合。

让我们来看一个现实生活中的集合例子。你收集什么东西吗？也许你收集旧唱片，你的收藏中的每张唱片都可以被唯一标识，重复的唱片则是用来交易或出售的。而且，无论你把唱片放在架子上时按什么顺序，它们仍然是同一组唱片。所以唱片收藏实际上就是一个集合。

同样，我们可以拥有一个绘画或邮票的集合。另一个集合是字母表，例如英语、俄语或希腊语字母表。使用这些字母表，我们可以构建语言。我们有自然语言（就像我刚才提到的那些）和形式语言。像C#、Java、C或Haskell这样的编程语言就是形式语言的例子。

数学中的集合通常用一个具有指示意义的大写字母来表示，例如 $R$ 表示唱片， $S$ 表示邮票，或 $A$ 表示字母表。如果我们有多个集合，我们可以使用下标来唯一标识它们： $A_{1}, A_{2}, A_{3}$ …

包含元素 $a$ 、 $b$ 和 $c$ 的单个集合的表示法是 $\{a, b, c\}$ 。这被称为显式定义。我们现在可以声明一个集合 $A$ 为 $A = \{a, b, c\}$ 。
当然，我们也可以有一个集合的集合： $C = \{\{a, b\}, \{c, d\}, \{a, c\}\}$ . 请注意，集合 $\{a, c\}$ 是唯一的，即使 $a$ 和 $c$ 已经是其他集合中的元素。
以下集合的集合无效： $\{\{a, b\}, \{b, a\}\}$ 。因为集合中的元素顺序被忽略，所以这个集合包含同一个集合两次，而集合也必须包含唯一的值。
现在假设我们有英语字母表 $E$ ，俄语字母表 $R$ 和希腊语字母表 $G$ 。字母表的集合表示为 $\{E, R, G\}$ 。

现在我们想表示 $a$ 是 $E$ 的元素。我们使用以下语法来实现： $a \in E$ 。
要表示 $\lambda$ （希腊字母lambda）不是 $E$ 的元素，我们使用表示法： $\lambda \notin E$ 。

我们可以比较集合。当集合包含完全相同的元素，不多也不少时，它们就被认为是相等的。 $\{a, b, c\} = \{a, b, c\}$ ， $\{a, b, c\} = \{c, b, a\}$ （记住，顺序被忽略）， $\{a, b, c\} \neq \{d, e, f\}$ ，以及 $\{a, b, c\} \neq \{a, \{b\}, c\}$ （集合 $\{b\}$ 不等于 $b$ ）。

到目前为止，我们只看到了显式定义的集合。我们也可以隐式定义集合。当一个集合包含太多无法一一列举的元素时，这尤其有用。例如，一个包含地球上所有国家的集合。这种集合的表示法如下： $\{x | \text{x is a country on Earth}\}$ 。你应该这样理解：“由所有x组成的集合，其中x是地球上的一个国家”。
一般来说，我们可以说一个隐式定义的集合形式为 $\{x | P(x)\}$ ，其中，在这个例子中， $P(x)$ 是“x是地球上的一个国家”这个命题。实际上 $P(x)$ 是一个函数，它接受参数x并返回x是否属于该集合。我们将在后面的博文中讨论函数。

为了表示任何给定（有限）集合中包含的元素数量，我们可以使用表示法 $|A|$ 。所以 $|\{a, b, c\}| = 3$ 和 $|E| = 26$ （其中E是英文字母表）。当然，这只有在我们的集合是有限的（我们可以数出元素数量）时才可能。

如果一个集合是空的（不包含任何元素）或者一个集合 $A = \{\}$ ，我们可以使用特殊符号 $\emptyset$ 。当然 $|\emptyset| = 0$ （空集包含 $0$ 个元素）。

当我们允许同一个元素在集合中出现多次，并且我们开始考虑元素的顺序时，我们称之为序列。序列的表示法就是将元素并排放置。例如，使用集合 $\{a, b, c\}$ ，我们可以构成序列a、ab、abc、baac、caab，但不能构成baad（因为d不在集合中）。

无限集合

到目前为止，我们看了有限集合。现在让我们看看一些无限集合。考虑所有数字的集合：1, 2, 3, 4… 理论上，我们总能给任何数字加1，所以我们永远无法停止计数。其中一些集合非常重要，以至于它们有了自己的符号。
首先，我们有自然数： $\mathbb{N} = \{0, 1, 2, 3, ...\}$ 。
如果我们加入负数，我们就得到了所有整数： $\mathbb{Z} = \{..., -3, -2, -1, 0, 1, 2, 3, ...\}$ 。
如果我们还允许分数，例如 $\frac{1}{2}$ （一半）或 $\frac{1}{4}$ （四分之一），那么我们就得到了有理数集合 $\mathbb{Q}$ 。
并非所有数字都可以表示成分数，例如pi（ $\pi$ ，半径为1的圆的周长）或 $\sqrt{2}$ 。当我们想包含这些数字时，我们得到实数集合 $\mathbb{R}$ 。

现在假设我们想要所有正自然数，即1, 2, 3…（不包括0）。我们可以用 $\mathbb{N}^+$ 来表示。同样，所有负数 -1, -2, -3…可以用 $\mathbb{Z}^-$ 来表示。当然，我们也可以使用 $\mathbb{Q}^+$ 、 $\mathbb{Q}^-$ 、 $\mathbb{R}^+$ 和 $\mathbb{R}^-$ 来表示正数或负数分数和实数。

我们可以用隐式定义来定义新的无限集合。例如，所有偶数的集合可以定义如下： $E = \{ x | x \in \mathbb{Z} \text{ and x is even}\}$ 。
所以这里 $E$ 是一个由所有x组成的集合，其中x是 $\mathbb{Z}$ （所有整数）的元素，并且x是偶数。

子集

如果集合A中的所有元素都属于另一个集合B，我们说A是B的子集。例如， $A = \{a, b, c\}$ 是 $B = \{x | \text{x is a letter in the English alphabet}\}$ 的子集，因为a、b、c都是英文字母。

更正式地说，我们可以说，如果A和B都是集合，并且对于每一个 $x \in A$ 都满足 $x \in B$ ，那么A是B的子集。

我们可以将此写为 $A \subset B$ 。由于在前面的例子中，A不包含B中的所有英文字母，所以我们也可以说B不是A的子集，这表示为 $B \not\subset A$ 。

根据上述定义，我们也可以说 $A \subset A$ ，或者A是它自身的子集。空集 $\emptyset$ 是所有集合（包括它自身）的子集。

当 $A \subset B$ ，但 $A \neq B$ ，那么我们说A是B的真子集。我们可以将其写为 $A \nsubseteq B$ 。
有时你可能会看到表示法 $A \subseteq B$ 来表示A是B的子集，A可能等于B，也可能不等于B。
在整个系列中，我将只使用 $A \subset B$ 。

当 $A \subset B$ 和 $B \subset A$ 时，则 $A = B$ 。

类似地，如果A是B的子集，我们可以说B是A的超集。这表示为 $B \supset A$ （这是子集符号的翻转）。当然，我们也可以使用 $B \supseteq A$ 来表示B是A的超集，B可能等于A，也可能不等于A。对于真超集，我们可以使用 $A \nsupseteq B$ 表示法。

当 $A \supset B$ 和 $B \supset A$ 时，则 $A = B$ 。

一些代码

我承诺过会尽量让这个系列具有一定的实用性。所以让我们来看一些代码。考虑以下使用你喜欢的.NET集合类的C#示例。

List<int> list = new List<int>();
list.Add(1);
list.Add(2);
list.Add(3);
list.Add(1);
int thirdItem = list[2]; // 0-based index.

列表现在包含项目1、2、3和1。我们还可以获取第n个位置的项目，这只有在我们知道列表中元素的顺序时才有用。基于此，我们可以得出结论，.NET中的List类不是一个集合。如果我们想在.NET中使用集合，我们可以使用HashSet<T>类。

HashSet<int> set = new HashSet<int>();
set.Add(1);
set.Add(2);
set.Add(3);
if (!set.Add(1))
{
    Console.WriteLine("Item 1 couldn't be added.");
}
//int secondItem = set[1]; // Doesn't compile.

因为集合只包含唯一项，所以可以生成每个项的哈希值，这意味着集合的查找时间比列表快得多（尤其是在列表大小增长时）。HashSet<T>可以与Dictionary<TKey, TValue>类进行比较，但没有值。

不幸的是，C#不知道列表生成器。在C#中处理无限集合也相当困难。比如说你想得到所有正偶数， $E^+ = \{ x | x \in \mathbb{N}^+ \text{ and x is even}\}$ 。我们有几个问题。首先C#中没有 $\mathbb{N}$ 。我们可以取Int32.MaxValue（但那会导致OutOfMemoryException）。所以我们只取小于或等于一百万的所有正偶数。

IEnumerable evens = from x in Enumerable.Range(1, 1000000)
                         where x % 2 == 0
                         select x;
List evaluatedEvens = evens.ToList();

在C#中，如果不费很大力气，类似这样的东西是我们能做的最接近的了。

这时，我被纠正了。Paulo Zemek指出，实际上利用yield关键字可以很容易地处理无限集合。下一个（控制台应用程序）示例对此进行了说明（尽管int最终会溢出…）。

static void Main(string[] args)
{
    foreach (int i in Evens().Take(10))
    {
        Console.WriteLine(i);
    }
    Console.ReadKey();
}

static IEnumerable Evens()
{
    return XToInfinity(1).Where(i => i % 2 == 0);
}

static IEnumerable XToInfinity(int start)
{
    int current = start;
    while (true)
    {
        yield return current;
        current++;
    }
}

但这仍然是很多打字工作…

让我们再看一门能更好地解决这类问题的语言，一门更接近实际数学的语言，Haskell。

evens = [ x | x <- [1..], x `mod` 2 == 0]

看，这就是了。请注意，代码实际上非常接近数学表示法。取所有x，其中x是[1..]（从1到无穷大）的元素，并且x是偶数。
我们可以轻松地获取这个无限集合的前10个元素，而不会导致程序崩溃或出现内存不足的异常。

*Main> take 10 evens
[2,4,6,8,10,12,14,16,18,20]

这不是关于Haskell的博客，所以我也不能深入解释它的功能，但我可以说Haskell是一种“惰性”语言，这意味着它不会计算列表中的元素，直到你真正需要它们为止。在这种情况下，它只会计算evens的前十个元素，从而避免占用我们的内存和CPU。

暂时就到这里。我们对集合进行了非常基础的介绍，但如果你不熟悉这些内容，它很快就会变得困难。所以我们慢慢来。下次，我们将组合集合并看看维恩图。

希望下次再见！

文章 IT中的数学 #1：基本集合论首发于 Sander's bits。