前言

要说到函数与类型,只要是个写带有类型系统的编程语言,都应该很熟悉,因为我们天天都会接触到。但是对于在范畴论上,或更广义地我们指在数学上的函数,以及类型的概念(因为数学上类型相等于只是集合,下面会提及),他们又或许又有不一样的面貌展现在我们的面前。

函数(Function)

函数只是一个过程(或者说是一个黑箱),因为它只负责接受某些参数,然后处理,最后返回一些返回值。这或许是大部分写命令式编程语言的人心中对于函数所理解的了,即使是对于使用函数式编程开发的人,函数的概念多多少少与数学上也是有出入的。正因为在不同领域对函数的定义与概念都不一样,因此先让我们定义函数这个概念究竟是什么。

概念

首先我们来回顾一下我在范畴论上一章对于态射(Morphism)与复合(Compose)的概念,且我们得知态射其实是可以被直接作为函数来看待的,在这里要再补充的是:对象(Object)在态射这个过程中不仅仅只是存在一个对象,而是可以有一个或多个对象在同时态射,就例如我们在数学上不仅可以定义两个整数为对象,然后把它们相加在一起(像 \(5 + 8\) 这样),而加法本身也是个函数,而且这条函数本身并不仅能接受 \(5\) 作为一个参数,然后返回 \(8\),而是根据具体这条函数的定义域(Domain)来决定所接受的参数都有什么(例如在这我们设为 \(\forall x.x \in \mathbb Z\)),再把集合内的所有整数加上另外一个整数(例如 map (+3) [1,2,3]\(x + 3\)),最后输出到新的集合 \(Y\) 上,正如下图这样:

集合 \(X\) 是作为定义域(Domain)出现的,然后我们把 \(X\) 当中的元素给态射到集合 \(Y\),即像 / 值域(Image / Range)上,因此使用映射关系也可以公理化成这样:\(X \xrightarrow[f]{} Y\)

函数关系(Relationship of function)

既然在概念上我们提到,函数之间的关系可以以集合映射的形式表示出来,因为这样可以更清晰地描述其中的关系。下面我们不妨来粗略地了解下函数的映射关系吧(详尽的定义可以参考维基)。

陪域与值域(或像)(Codomain and Range(or Image))

要谈及到陪域的概念,首先我们需要了解一下值域(或像)的概念,值域就相等于函数实际输出的集合,例如我们说有一条函数 \(f : \mathbb Z \mapsto \mathbb Z\),定义为 \(f(x) = x + 2\),而定义域的则取于 \([0,2]\) 区间之间,因此对于给定的输入 \(0, 1, 2\),可得到实际输出 \(2, 3, 4\),实际上这些也就是值域内的对象。

那么培域(Codomain)呢?它其实就相当于一个于一个函数的可能输出范围,那什么叫 "可能输出的范围" 呢?由于我们上面给定的定义域只有 \(0, 1, 2\) 这三个数,但我们千万不能忽视除了这几个数以外,对于这条函数来讲其实是可以接受其他整数 \(x \in \mathbb Z\) 作为输入的,所以其实我们可能还有 \({...,-3,-2,-1,0,1,2,3,...}\) 等等的作为输入的集合,然后对应的可能输出也就是培域(也是值域的超集,\(Codomain \supseteq Range\))了。

单射函数(Injective function)

相较于满射函数,单射函数也就是单独,单一的意思,也即是对于定义域所有的对象,并不会映射到值域上的所有对象,只有部分被一一对应地映射。换句话说就是值域与培域在这种情况下是不相等的,此时值域必然会小于培域(如果相等的话就变成满射函数了)。

具体定义为: 若满足 \(\forall x, y \in X, f(x) = f(y) \implies x = y\),则 \(f : X \to Y\) 为一单射函数。

满射函数(Surjective function)

满射的含义为完满,完全,所有的意思,也就是指对于值域上的所有对象,都必定至少存在一个映射由定义域映射过去,因此我们 "不会错过" 任何一个输出,即便出现多对一映射的情况。所以说对于所有输出不仅仅是可能的,而且是必然的,最终的结果就是值域会直接等同于培域。

具体定义为: 若满足 \(\forall y \in Y, \exists x \in X, f(x) = y\),则 \(f : X \to Y\) 为一满射函数。

双射函数(Bijective function)

透过观察在概念中 \(X \xrightarrow[f]{} Y\) 的例子我们得知,左边的集合(定义域)与右边集合(像 / 值域)的对象是全部对应起来的,因为我们上面的定义域为 \(\forall x.x \in \mathbb Z\)(也就是对于所有 \(x\),它们都属于整数这个集合),且是一一对应的,也就是 \(1 \to 2\)\(2 \to 3\)\(3 \to 6\) 这样,它们并不会形成类似多对一,一对多的关系。因此我们可以把这种关系称之为双射(满射且单射)。

反函数与原像(Inverse function and Preimages)

函数可逆性(Function invertibility)

并不属于函数范畴的态射关系

上面已经列出部分函数的基础关系,下面我们来看一些 "很像函数但又并不是函数" 的函数。

多值函数(Multivalued function)

由于数学上函数的定义每一个输入都只能够对应一个输出,而多值函数也就是一对多的字面意思,所以多值函数并不是一条函数。在数学上最显然的例子就是求根公式得出来的结果有可能是正或者负,如果得出来的结果例如只有一个正整数或者负整数那就是很正常的一条函数,但若果得出来的结果可能是出现多个的,例如 {\(-2, 2\)},那这个就是属于多值函数了。而之所以为什么我们看到当今计算机语言的函数并不能直接拥有多返回值(顶多也只能够返回一个 Array List Tuple Pair Set 之类的容器),究其原因其实也在这里。

偏函数(Partial function)

偏函数指的是在定义域内,有一个或多个对象并未映射到值域内,而这种情况就好比我们日常开发的时候,写一条函数,接受两个参数,但第一个参数从始至终都未在函数体内被间接或直接地引用过,也就是 Unused parameter,这种看似是能写的出来的函数实际上也并不是一条函数。

范畴关系(Category Relationship)

请不要忘记我们的目标是什么,在上面介绍完函数的基本关系之后并不是代表就结束了,那仅仅只是函数上关系而已,而我们还有对于范畴论内的态射关系没谈呢!所以现在让我们来开始一起看看吧。

同态(Homomorphism)

同态含义为 "相同的形态",也就是指在映射时保持两个代数结构上它们相同形态不变。对于函数上有不同种类的函数类型(例如上面单射 / 满射 / 双射函数等等),在范畴论上的态射种类也就被称为同态了。

单同态(Monomorphism(Monic))

单同态在范畴论上的概念几乎等同于集合论(或集合范畴 \(C_{Set}\))的单射函数,对于范畴 \(C\) 内,我们有 \(g_x : C \to A\) 以及 \(f : A \to B\),对于态射 \(g_1, g_2\),若它们均与 \(f\) 结合,即 \(f \circ g_1\)\(f \circ g_2\) 隐含了 \(g_1 = g_2\)(这里我们可以左消除(Left cancellable)\(f\),像这样:\(\require{cancel} \cancel{f \circ} g_1 = \cancel{f \circ} g_2\)),满足这个条件时我们称 \(A \rightarrowtail B\) 是单同态的。

满同态(Epimorphism(Epic))

满同态在范畴论上的概念几乎等同于集合论(或集合范畴 \(C_{Set}\))的满射函数,在这里我们不妨也给出 \(f : A \to B\) 以及 \(g_x : B \to C\),对于态射 \(g_1\), \(g_2\),若它们均与 \(f\) 结合,即 \(g_1 \circ f\)\(g_2 \circ f\) 隐含了 \(g_1 = g_2\) (因为我们可以右消除(Right cancellable) \(f\),像这样:\(g_1 \require{cancel} \cancel{\circ f} = g_2 \cancel{\circ f}\)),所以 \(A \twoheadrightarrow B\) 是满同态的。

同构(Isomorphism)

同构的皆指在范畴在态射之间保持了不变的结构,换句话说就是一样的结构,假设我们有态射 \(f : A \to B\),若这个态射是同构关系,那么它肯定保留了可逆以及对称性,所以有 \(g : B \to A\)。而因每个对象本身都存在单位元,例如每次当 \(g \circ f\) 绕回来的时候其实也就等同于 \(id_A\),因此保有如下性质:\(g \circ f = id_A\) 以及 \(f \circ g = id_B\)

而在 Haskell 中我们能很简单的定义一个类型表示同构关系:

1
type ISO a b = (a -> b, b -> a)

总结

本篇略略介绍了一些简单的基础函数与同态的关系,所以当然关系是不止这么一点的,后续会慢慢提及到。而了解清楚这些关系之后在写代码时也有助于看清楚函数背后的细节与作用,使逻辑条理更为清晰。