(这是关于《范畴论》一系列回答的第十篇,紧接在问题:”极限的含义?“ 之后,小石头将在本篇中与大家一起讨论单子。
)单子(monad)的哲学解释大家可以参考莱布尼兹的《单子论》,这里仅仅讨论数学中的单子。在引入单子概念之前,我们先做一些准备。首先,让我们复习一下以前介绍过的各种复合操作:态射 f: A → B, g: B → C 的复合还是态射:gf: A → C具体定义由各个范畴结合态射的定义给出;函子 F: A → B,G: B → C 的复合还是函子:GF: A → C定义为:GF(f) = G(F(f)), GF(A) = G(F(A))自然变换 α: F → G, β: G→ U (F, G, U: A → B, α, β: ObA → MorB) 的复合还是自然变换:β∘α: F → U(β∘α: ObA → MorB)定义为:β∘α(A) = β(A)α(A)考虑到,自然变换复合定义的特殊性,尤其是与其他复合联用时,我们一般不省略 自然变换 之间的 复合 符号。自然变换 α: F → G(F, G: A → B,α: ObA → MorB)与 函子 U: B → C 的复合是自然变换:Uα: UF → UG(Uα: ObA → MorC)定义为:Uα(A) = U(α(A))函子 F: A → B 与 自然自然变换α: G → U(G, U: B → C,α: ObB → MorC) 的复合是自然变换:αF: GF → UF(αF: ObA → MorC)定义为:αF(A) = α(F(A))自然变换 α: F → G, β: U→ V (F, G: A → B, α: ObA → MorB, U, V: B → C, β: ObA → MorB) 的星乘还是自然变换:β∗α: UF → VG(β∗α: ObA → MorC)定义为:β∗α = βG∘Uα =Vα∘βFUα: UF → UG, βG: UG → VG, βG∘Uα: UF → VG; βF: UF → VF, Vα: VF → VG, Vα∘βF: UF → VG.然后,对于平行反向函子 F: A ⇄ B: U,回忆,伴随 F ⊣ B 的前3种定义:自然变换 η: 1ᴀ → UF(称为 单位),对于每个A ∈ObA, η(A) 都是 A 到 U 的 泛映射;如果 对于任意 A ∈ObA, B ∈ObB,都存在 自然双射 φ: Hom(F(A), B) ≅ Hom(A, U(B)) :ψ (称为 附属形式);自然变换 ε: FU → 1ʙ (称为 余单位),对于每个B ∈ObB, ε(B) 都是 B 到 F 的 余泛映射;以及, 第 1,3 种定义 分别 和 第2种定义 之间的关系:η(A) = φ(1ғ₍ᴀ₎) ,f = φ(g) = U(g)η(A);ε(B) = ψ(1ᴜ₍ʙ₎),g = ψ(f) = ε(B)F(f);接下来,我们研究 第 1,3 种定义之间的关系。根据 A 的任意性,可令,A = U(B)则,F(A) = FU(B)。又,令,f = 1ᴜ₍ʙ₎则,g = ψ(f) = ψ(1ᴜ₍ʙ₎)再根据前面的关系:ε(B) = ψ(1ᴜ₍ʙ₎)有,g = ε(B)将以上结果,带入前面的关系:f = φ(g) = U(g)η(A) 得到 ①:1ᴜ₍ʙ₎ = f = φ(g) = U(ε(B))η(U(B))即,1ᴜ = Uε∘ηU同理,令 B = F(A),g = 1ғ₍ᴀ₎,根据前面的关系,最终,可得到 ②:1ғ = εF∘Fη结果 ① 和 ② 就是 第 1,3 种定义 之间的关系,绘制成交换图如下:我们,称 ① 和 ② 为三角恒等式。三角恒等式 可以作为,伴随的第 4 种定义的条件,即,对于平行反向函子 F: A ⇄ B: U,如果,存在自然变换η: 1ᴀ → UF 和 ε: FU → 1B 并且满足 三角恒等式,则 F 和 U 伴随。上面已经从 前 3 种定义 推出了 定义4,现在只要从 定义4 推导出 定义2,就可以 证明 这些定义的 等价性了。我们,令:φ(g: F(A)→B ) = U(g)η(A);ψ(f: A → U(B) ) = ε(B)F(f);则有,φ(ψ(f)) = φ(ε(B)F(f)) = U(ε(B)F(f))η(A) = U(ε(B)) U(F(f))η(A)∵ η 的自然性∴ =U(ε(B)) η(U(B)) f∵ 三角恒等式 ①∴ = 1ᴜ₍ʙ₎ f = fψ(φ(g)) = ψ(U(g)η(A)) = ε(B)F(U(g)η(A)) = ε(B)F(U(g)) F(η(A)) ∵ ε 的自然性∴ = gε(F(A)) F(η(A))∵ 三角恒等式 ②∴ = g 1ғ₍ᴀ₎ = g于是,就是证明了 φ 和 ψ 是互逆的双射。关于φ 和 ψ 的自然性 也很容易验证(留给大家思考),这样以来我们就推出了定义2。有了以上准备,接下来我们开始引入单子的概念。单子在上面的伴随中,我们以 范畴 A 为焦点, 如果,令 T = UF:A → A,1 = 1ᴀ ,则 伴随的单位,可记为:η: 1 → T再考虑 余单位 ε: FU → 1ʙ,我们分别在ε左右复合U和F,可得到:UεF: UFUF → U1ʙF而,UFUF = TT = T² , U1ʙF = UF,于是,令μ = UεF,则有 自然变换:μ: T² → T令 B = F(A) 为参数,带入 三角恒等 1ᴜ₍ʙ₎ = Uε(B)∘ηU(B) 得到:1ᴜғ₍ᴀ₎ = UεF(A)∘ηUF(A)1ᴛ₍ᴀ₎ = μ(A)∘ηT(A)即,1 = μ∘ηT对 三角很等式 1ғ₍ᴀ₎ = εF(A)∘Fη(A) 两边应用 函子 U,有:U(1ғ₍ᴀ₎) = U(εF(A)∘Fη(A))由于,函子将幺态射映射到幺态射,所以,等式左边 = 1ᴜғ₍ᴀ₎根据,函子的保持复合性,知 ,等式右边 = UεF(A)∘UFη(A)等式两边关联的就得到:1ᴜғ₍ᴀ₎ = UεF(A)∘UFη(A)1ᴛ₍ᴀ₎ = μ(A)∘Tη(A)即,1 =μ∘Tη将上面的得到的结果绘制成交换图Ⅰ,如下 :另一方面,考虑 B 中的 任意 态射 f: X → Y, 根据自然变换 ε: FU → 1ʙ 的自然性,有如下交换图:令,X = FU(Y),则有:这时我们发现 f, ε(Y) 同时属于 Hom(FU(Y), Y),于是 可以令 f = ε(Y),则有:又令,Y = F(A),则有:再对上图应用 函子 U ,将其从范畴 B 映射 到范畴 A,有:将 图中 表达式 改写成 T 和 μ 和形式, 最后 得到 如下交换图Ⅱ:对应关系式为:μ∘μT = μ∘Tμ综上,我们就从 伴随函子F: A ⇄ B: U 得到了:定义在 范畴 A 上的 函子 T: A → A ,以及两个 使得 图 Ⅰ 和 Ⅱ 可交换 的 自然变换 η: 1 → T 和 μ: T² → T ,我们 称 T(以及 η 和 μ)为 单子。Eilenberg-Moore 范畴以上,是从 伴随 F: A ⇄ B: U 得到了 A 上的 单子 T,反过来 从 单子 T: A → A也可以 构造 伴随 F: A ⇄ B: U,这件事 最早 是 由 Eilenberg 和 Moore 通过构造 Eilenberg-Moore 范畴,来实现的。关于 范畴 A 的 Eilenberg-Moore 范畴,记为: Aᵀ。Aᵀ 对象 是 由 A 中任意对象 A 和 映射 h: T(A)→ A 组成的 序对 (A, h),并且要求满足条件:1ᴀ = h∘η(A)h∘μ(A) = h∘T(h)即,使得下二图可交换:我们称(A, h) 为 T-代数,A 称为 代数的 底对象,h 称为 代数的 构造映射,条件1(上面左图)称为 代数的 单位律,条件2(上面右图)称为 代数的 结合律。Aᵀ 中的态射 与 A 保持一致,即㈠,f: (A, h) → (A', h')当且仅当 f: A → A'进而 A 中的 态射的 复合 也就 无缝迁移到了 Aᵀ。由 T-代数 组成 的 范畴 Aᵀ ,就是 我们要构造 的 伴随 F: A ⇄ B: U 中的 B。函子 U: Aᵀ → A 很自然的可以定义为:U(A, h) = A, U(f) = f接着,观察 单子 的 换图 Ⅰ和 Ⅱ 中的关系式:1(A) = μ(A)∘ηT(A)μ(A)∘μT(A) = μ(A)∘Tμ(A)如果 令,h = μ(A),Ã = T(A),则改写为:1ᴀ = h∘η(Ã)h∘μ(Ã) = h∘T(h)刚好满足 T-代数 的 单位律 和 结合律,于是 (Ã, h) 是 Aᵀ 的对象,所以 我们可以定义 函子 F: A → Aᵀ 为:F(A) = (T(A), μ(A)), F(f) = T(f)显然,有:UF(A) = U(T(A), μ(A)) = T(A)即,UF = T于是,η 可记为:η: 1ᴀ → UF再考虑,自然变换 ε: FU → 1ᴀᵀ,有:ε(A, h): FU(A, h)→ (A, h)因为 FU(A, h) = F(A) = (T(A), μ(A)) ,所以:ε(A, h): (T(A), μ(A))→ (A, h)又根据 上面㈠ 处 Aᵀ 的规定,有:ε(A, h): T(A) → A而,恰恰有:h: T(A) → A所以,我们可以定义 ε 如下:ε(A, h) = h到此为止我们就定义出来了 函子 F :A ⇄ Aᵀ : U和 自然变换 η: 1ᴀ → UF与ε: FU → 1ᴀᵀ,根据这些定义,对于 任意 A ∈ ObA, 结合 单子的图Ⅰ交互性,有:εF(A)∘Fη(A) = ε(T(A), μ(A))∘F(η(A)) = μ(A)∘Tη(A) = 1ᴛ₍ᴀ₎ = 1ᴜ₍ғ₍ᴀ₎₎ = U(1ғ₍ᴀ₎) = 1ғ₍ᴀ₎对于 任意 (A, h) ∈ ObAᵀ ,应用 T-代数 的 单位律,有:Uε(A, h)∘ηU(A, h) = U(h)∘η(A)= h∘η(A) = 1ᴀ = U(1ᴀ) = 1ᴜ₍ᴀ₎这样就验证了 “三角恒等式” 成立 ,故,F 和 U 就是 我们要构造的 伴随。闭包最后,我们举一个单子的实际例子,以加深对其的理解。回忆前面的 偏序范畴 Poset,其态射 就是 偏序关系:A → B iffA ≤ B态射的复合,就是 偏序的传递性:A ≤ B ∘ B ≤ C = A ≤ C设,T: Poset → Poset 是 Poset 上的 单子 ,则,首先 T 是函子,于是有:T(A ≤ B) = T(A)≤ T(B)故,T 是单调递增的。要使得 η: 1 → T 存在,则,η(A): A ≤ T(A)就必须存在,故,显然 T 是 上升的。要使得 μ: T² → T,存在,则,μ(A): T²(A) ≤ T(A)就必须存在,而,又有:T(A ≤ T(A)) = T(A) ≤ T²(A)故,只能是:T²(A) = T(A)当然,也是,T(A) = T²(A) = T³(A) = ...我们,称 这样的 T 为 闭包,一般记为 Ā= T(A)。可以验证,闭包 满足 单子的要求:μ(A)∘ηT(A) = T²(A) ≤ T(A) ∘ T(A) ≤ T²(A) =μ(A)∘Tη(A) =T²(A) ≤ T(A) ∘ T(A ≤ T(A)) =T²(A) ≤ T(A) ∘ T(A) ≤ T²(A) =T²(A) ≤ T²(A)=T(A) ≤ T(A) = 1ᴛ₍ᴀ₎μ(A)∘μT(A) = T²(A) ≤ T(A) ∘ T³(A) ≤ T²(A) = μ(A)∘Tμ(A)故,闭包的确是单子。闭包和单子是函数式编程中很重要的两个概念,由于本系列回答限制于数学的角度,因此不会涉及计算机语言的内容,以后有机会再和大家一起讨论《范畴论》在计算机语言中的应用。好了,这篇回答就先到这里,关于单子还有许多内容,我们下一篇回答再继续讨论!(最后,由于小石头数学水平有限,出错在所难免,欢迎批评指正,同时感谢大家阅读!)