11 范畴论入门
11 范畴论入门
“范畴论不是高深的数学——它是关于结构之间关系的学问，恰好能指导我们如何正确地设计软件。”
11.1 什么是范畴论
范畴论（Category Theory） 是数学的一个分支，研究数学结构之间的映射和关系。它在函数式编程中提供了统一的抽象框架。
11.1.1 为什么程序员要学范畴论
| 原因 | 说明 |
|---|---|
| 统一抽象 | Functor、Monad 等概念都来自范畴论 |
| 正确性保证 | 定律（Laws）确保代码行为正确 |
| 组合性 | 范畴论是关于组合的数学 |
| 可重用模式 | 同一模式适用于不同领域 |
11.2 范畴（Category）
11.2.1 定义
一个范畴 C 由以下组成：
- 对象（Objects） 的集合
Ob(C) - 态射（Morphisms） 的集合
Hom(C)，每个态射f: A → B连接两个对象 - 组合运算（Composition）
∘，满足：- 结合律：
(f ∘ g) ∘ h = f ∘ (g ∘ h) - 单位元：对每个对象 A，存在
id_A: A → A，使得f ∘ id = id ∘ f = f
- 结合律：
11.2.2 程序中的范畴
在编程中，最常见的范畴是：
| 范畴 | 对象 | 态射 | 组合 | 单位元 |
|---|---|---|---|---|
| 类型范畴 (Hask) | 类型 | 函数 | 函数组合 | id |
| Set | 集合 | 函数 | 函数组合 | 恒等函数 |
| 预序集 (≤) | 元素 | ≤ 关系 | 传递性 | 自反性 |
| 群 | 群元素 | 群运算 | 群乘法 | 单位元 |
-- Hask 范畴中的组合和单位元
-- 态射：函数
f :: Int -> String -- 从 Int 对象到 String 对象的态射
g :: String -> Bool -- 从 String 对象到 Bool 对象的态射
-- 组合：函数组合
g . f :: Int -> Bool
-- 单位元
id :: a -> a
-- 结合律
h . (g . f) ≡ (h . g) . f
-- 单位元律
id . f ≡ f
f . id ≡ f
JavaScript：
// 组合满足结合律
const f = x => x + 1;
const g = x => x * 2;
const h = x => x - 3;
const compose = (...fns) => x => fns.reduceRight((acc, fn) => fn(acc), x);
// 结合律
compose(h, compose(g, f))(5) === compose(compose(h, g), f)(5); // true
// 单位元
const id = x => x;
compose(id, f)(5) === compose(f, id)(5) === f(5); // true
11.3 函子（Functor）
11.3.1 范畴间的函子
函子（Functor） 是范畴之间的映射，保持范畴结构。
给定范畴 C 和 D，函子 F: C → D 包括：
- 对象映射：
F(A)将 C 的对象映射到 D 的对象 - 态射映射：
F(f)将 C 的态射映射到 D 的态射 - 保持组合：
F(g ∘ f) = F(g) ∘ F(f) - 保持单位元：
F(id_A) = id_(F(A))
11.3.2 编程中的函子
-- 在 Hask 范畴中，endofunctor 将 Hask 映射到自身
class Functor f where
fmap :: (a -> b) -> f a -> f b
-- 定律
fmap id ≡ id -- 保持单位元
fmap (g . h) ≡ fmap g . fmap h -- 保持组合
-- Maybe 函子
-- 对象映射: a → Maybe a
-- 态射映射: (a → b) → (Maybe a → Maybe b)
instance Functor Maybe where
fmap _ Nothing = Nothing
fmap f (Just a) = Just (f a)
JavaScript：
// Functor 定律验证
const Maybe = {
of: x => ({ type: 'Just', value: x }),
nothing: () => ({ type: 'Nothing' }),
map: (fn, m) => m.type === 'Nothing' ? m : Maybe.of(fn(m.value)),
};
const id = x => x;
const f = x => x + 1;
const g = x => x * 2;
// 定律 1: fmap id ≡ id
assert.deepEqual(Maybe.map(id, Maybe.of(5)), Maybe.of(5));
// 定律 2: fmap (g . f) ≡ fmap g . fmap f
const m = Maybe.of(5);
assert.deepEqual(
Maybe.map(x => g(f(x)), m),
Maybe.map(g, Maybe.map(f, m))
);
11.4 自然变换（Natural Transformation）
11.4.1 定义
自然变换 是函子之间的映射。给定函子 F, G: C → D，自然变换 η: F ⟹ G 是一族态射 η_A: F(A) → G(A)，满足自然性条件：
对于任意态射 f: A → B,
G(f) ∘ η_A = η_B ∘ F(f)
即：下面的图表交换
F(A) --η_A--> G(A)
| |
F(f) G(f)
| |
v v
F(B) --η_B--> G(B)
11.4.2 编程中的自然变换
-- 自然变换的类型签名
-- ∀ f. Functor f => f a -> g a
-- 必须对所有 a 成立，不关心 f 的内部结构
-- 从 Maybe 到列表的自然变换
maybeToList :: Maybe a -> [a]
maybeToList Nothing = []
maybeToList (Just x) = [x]
-- 从 Maybe 到 Either 的自然变换
maybeToEither :: Maybe a -> Either () a
maybeToEither Nothing = Left ()
maybeToEither (Just x) = Right x
-- 自然性条件验证
-- maybeToList . fmap f ≡ fmap f . maybeToList
-- 对于任何 f 都成立
JavaScript：
// 自然变换：Maybe → Array
const maybeToArray = (m) =>
m.type === 'Nothing' ? [] : [m.value];
// 验证自然性：maybeToArray . map(f) = map(f) . maybeToArray
const f = x => x * 2;
const m = Maybe.of(5);
// 两种路径等价
const path1 = maybeToArray(Maybe.map(f, m)); // [10]
const path2 = maybeToArray(m).map(f); // [10]
assert.deepEqual(path1, path2); // 成立
11.5 组合律与结合律
11.5.1 组合律（Composition Law）
-- 函数组合的结合律
-- (h . g) . f ≡ h . (g . f)
-- 实际验证
let f = (+1)
let g = (*2)
let h = (^3)
((h . g) . f) 3 == h . (g . f) $ 3 -- True
-- 在 Functor 中
fmap (h . g . fmap f) ≡ fmap h . fmap g . fmap (fmap f)
11.5.2 从范畴论看 Monad
-- Monad 是自函子范畴上的幺半群
-- 这句话的含义：
-- 1. "自函子"：Functor (Hask → Hask)
-- Monad 的 kind 是 (* -> *)
-- 它将类型映射到类型
-- 2. "幺半群"：有单位元和结合律的代数结构
-- 单位元：return :: a -> m a
-- 结合： (>>=) :: m a -> (a -> m b) -> m b
-- 3. "范畴上"：在自函子范畴中
-- 对象：Functor（如 Maybe, [], IO, Either e）
-- 态射：Natural Transformation
-- 组合：Monad 组合（通过 Kleisli 范畴）
-- Kleisli 范畴
-- 对象：类型
-- 态射：a → m b（Kleisli 箭头）
-- 组合：(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
-- 单位元：return
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g
-- 定律
return >=> f ≡ f
f >=> return ≡ f
(f >=> g) >=> h ≡ f >=> (g >=> h)
JavaScript：
// Kleisli 组合
const kleisliCompose = (f, g) => x => f(x).flatMap(g);
// Maybe 的 Kleisli 组合
const safeSqrt = x => x >= 0 ? Maybe.of(Math.sqrt(x)) : Maybe.nothing();
const safeDiv = a => b => b === 0 ? Maybe.nothing() : Maybe.of(a / b);
const sqrtOfDiv = kleisliCompose(safeDiv(100), safeSqrt);
sqrtOfDiv(4); // Maybe(5)
sqrtOfDiv(-1); // Nothing（除法结果为负数）
sqrtOfDiv(0); // Nothing（除以零）
11.6 半群与幺半群
11.6.1 半群（Semigroup）
class Semigroup a where
(<>) :: a -> a -> a
-- 满足结合律：(a <> b) <> c == a <> (b <> c)
-- 实例
instance Semigroup [a] where
(<>) = (++) -- 列表连接
instance Semigroup Int where
(<>) = (+) -- 加法（或 *）
instance Semigroup String where
(<>) = (++)
11.6.2 幺半群（Monoid）
class Semigroup a => Monoid a where
mempty :: a
-- 满足单位元律：
-- mempty <> x == x
-- x <> mempty == x
instance Monoid [a] where
mempty = []
instance Monoid Int where
mempty = 0 -- 加法单位元
-- 使用
mconcat :: Monoid m => [m] -> m
mconcat = foldr (<>) mempty
mconcat [[1,2], [3,4], [5,6]] -- [1,2,3,4,5,6]
Rust：
trait Semigroup {
fn combine(self, other: Self) -> Self;
}
trait Monoid: Semigroup {
fn empty() -> Self;
}
impl Semigroup for String {
fn combine(mut self, other: Self) -> Self {
self.push_str(&other);
self
}
}
impl Monoid for String {
fn empty() -> Self { String::new() }
}
11.7 业务场景
11.7.1 MapReduce 的范畴论视角
// MapReduce = Functor Map + Monoid Reduce
const mapReduce = (mapFn, reduceFn, empty) => (data) =>
data.map(mapFn).reduce(reduceFn, empty);
// 单词计数
const wordCount = mapReduce(
line => line.split(' ').reduce((acc, word) => ({ ...acc, [word]: 1 }), {}),
(a, b) => Object.entries(b).reduce((acc, [k, v]) => ({ ...acc, [k]: (acc[k] || 0) + v }), a),
{}
);
11.8 小结
| 要点 | 说明 |
|---|---|
| 范畴 | 对象 + 态射 + 组合 + 单位元 |
| 函子 | 范畴间的映射，保持结构 |
| 自然变换 | 函子之间的映射 |
| 半群/幺半群 | 带/带单位元的结合运算 |
| Monad | Kleisli 范畴上的幺半群 |
扩展阅读
- Category Theory for Programmers — Bartosz Milewski
- Category Theory for Computing Science — Barr & Wells
- Seven Sketches in Compositionality — Fong & Spivak
下一章：12 函数式响应式编程