在入坑接触 Haskell 一段时间后,碰到很多类似 Functor Applicative Monad 等等这些诸如此类的 “魔法”,虽然有时候用是会用了,利用各种自定义的 Monad instance 也实际优化了 FP (Functional Programming) 工程上的代码,但是回头一看 Monad(单子)这个神奇的词,仔细想想又并不这么简单能够解释,一查发现其中又牵涉出 Monoid(么半群) Semigroup(半群) 等等这些群论以至于范畴论上的概念出来。于是乎为了能够 彻底弄清楚这一大堆东西 (mǎn zú hào qí xīn) (顺便记录下学习的过程),特意开了本篇作为学习笔记,也希望能够记录这个入坑 猫论 (Category Theory) 到入土的心路历程(笑。

概念(Concept)

研究范畴就是试图以“公理化”的方法抓住在各种相关连的“数学结构”中的共同特性,并以结构间的“结构保持函数”将这些结构相关起来。因此,对范畴论系统化的研究将允许任何一个此类数学结构的普遍结论由范畴的公理中证出。

范畴论这门学问,虽然分类上是属于数学的基础内容,但个人(以作为 Haskeller 的角度)反倒觉得像是一门 “数学上的抽象语言”。就如同上面引文提及:它负责对数学结构中的共同特性,加以公理化的形式把这一个个的数学结构连接起来。举个例子:就如同数学上最简单的加减乘除这些 “二元运算”,均能被视为是一种连接两个数学结构之间的一个公理化的连接,因此才被称为 “二元运算”。

对象与态射(Object and Morphism)

通俗地讲,一个最简单的范畴结构可以由一个 对象(Object)态射(Morphism) 组合而成的,一个对象可以是任何东西(例如一个自然数或是个英文字母等等),而态射就相等于对象变换的过程,然后把一个个对象之间像是加上了一个个箭头(Arrow)一样将它们逐一连接起来,首先由对象 $A$ 态射到对象 $B$ ,最终由对象 $B$ 再态射到对象 $C$,正如这样:$$ A \to B \to C $$ 从上面我们可以很清晰的看到似乎就只是加上了箭头作为对象之间的连接,就形成了一个包含三个对象,两次态射的范畴了。

组合(Composition)

现在我们要提及到另一个重要的概念:组合(Composition)。上面对象与态射的小章节已经举出了一个简单的范畴例子,实际上我们可以为上面的态射给命名一下,例如改成这样:$$ A\xrightarrow[f]{} B \xrightarrow[g]{} C $$ 于是乎现在会更加直观地看到态射的名字了,我们设对象 $A$ 到 $B$ 的态射称为 $f$ ,而从对象 $B$ 到 $C$ 的态射为 $g$,最终由于对象 $A$ $B$ $C$ 会透过态射形成一个具备可传递性质的范畴,对象 $A$ 态射到 $C$ 的时候就会形成一个态射的组合(Composition of morphism),因此可以演变成这样:$$ A \xrightarrow[g \circ f]{} C $$ 我们看到上面由 $A$ 到 $C$ 的过程实际就是把 态射 $g$ 和 $f$ 给组合起来,形成一个新的复合态射,称之为 $g \circ f$。

在 Haskell 上的函数组合

众所周知很多图灵完全的编程语言上,函数不仅仅只能接受一个或多个参数,并且返回一个返回值,而是可以在满足下列至少任一条件:

  1. 一个函数接受一个或多个函数作为输入
  2. 输出一个函数

的情况下,作为一个普通函数使用,而这一概念也就是为人熟知的 高阶函数(Higher-order function)。那么当然在 Haskell 中也不例外,比方说我们现在有两条函数:

1
2
trim  :: String -> String
lower :: String -> String

分别是首先对字符串清除空格和后续的把字符串转换为全小写的函数。现在我们可以简单地把它们组合在一起,形成一个复合函数,在 Haskell 里面以 Point-free 形式写出来的代码大概像是这样:lower . trim,就已经成为了一个简单的函数组合了!

组合的特性(Properties of Composition)

组合(Composition)有两个非常重要的特性,在任何范畴内都必须满足这些特性,才能被称之为组合。

结合律(Associative Property)

组合是可结合的,也就是指出一个二元运算(这里是组合)只要它们算子(态射)的位置没有被改变,那就不会对整个组合过程的结果产生影响,也就是即使我们给组合加上改变优先级的运算符(例如括号),也并不会改变整个过程的结果。现在给出三个对象,它们分别是 $f$,$g$,$h$。然后把它们组合到一起:$$(h \circ g) \circ f = h \circ (g \circ f) = h \circ g \circ f$$ 最终可以看出它们的结果均是恒等的。

单位元(Identity)

单位元就如同一个特殊的单位(Unit),任何对象与其组合结果都会返回对象自身:$$ A \xrightarrow[id_A]{} A $$ $$f \circ id_A = id_A \circ f = f $$ 但要切记,上面的单位元 $id_A$ 依旧是一种态射,只不过组合后的结果还是落入了与 $f$ 同一个范畴内。就如同 $2 * 1$一样($1$ 是乘法单位元),它的运算结果永远都只会是整数(这里的范畴可以是整数乘法群,且群论上已定义了封闭性,所以结果不会是其他什么像是字符串,其他类型的自然数等等的这类东西),且最终它运算得出来的结果都会是等于 $2$,也就是等于自身,因此 $1$ 便符合了作为乘法单位元的特性。

组合的哲学(Philosophy of Composition)

要讲到组合的本质,它不仅仅只是在 物理学 / 数学 领域下某些分支的概念,或是函数式编程领域公理化或简化实际问题的 “东西”。从计算机的角度出发的话,它表示成一个个的过程,例如说实际编写 Haskell / Java / C++ 等等这些 Higher-Level 编程语言的代码,经过编译这个过程,实际上看似也很类似于态射这个概念,然后把这些代码 “自然转换” 为机器读的懂的东西,最终再由承载执行该语言的虚拟机,或者是 Runtime 负责运行,这一系列的过程连接起来也就形成了一个组合,而这个组合最终代表的就是一个完整的范畴,甚至某种程度上我们可以说我们日常生活遇到的各种事情都可以是一个范畴,而不仅仅是一个集合。范畴本身不仅可以被当成一个分类,而且他还可以把多个小分类给 “连接” 起来,解决一个很复杂很困难的事。在计算机领域最为直接的例子就是现代 CPU 的架构,其逻辑或线路布局复杂程度显然相当的高,但还是分出了 ALU,CU,寄存器,各种总线 等等的这些概念,然后把它们组合在一起运行。其次也就是我们日常编写代码时,如果没有这样化简归纳成一个个范畴的概念,那么现在的程序员可能每时每刻都只能用二进制去编写程序了,导致编写一个程序的门槛不知道高了多少多少,计算机领域的发展也就十分局限了。

总结(Conclusion)

以上便是本章节的内容了,本篇作为第一节可能会较少讲述实质在范畴论上的内容,而概念较多也是为了帮助自己和读者能够理解及学习到范畴论上的概念,作为日后深入范畴论的一个垫脚石。

外部链接(Outside Links)

本文部分内容参考或引用至下列网页,也可供作为额外的延伸资源帮助阅读: