Category: The Essence of Composition - 范畴：复合的本质

Link to Blog

<译> 范畴：复合的本质

A category consists of objects and arrows that go between them.

“范畴”是个很简单的概念，一个“范畴”由“对象”和对象间的“箭头”组成。范畴的本质是“复合”。“箭头”是可“复合”的。若已有从对象A到B的箭头和从对象B到C的箭头，那么必然存在一个从A到C的箭头，即前两者的“复合”。

这里的“对象”并非是面向对象编程世界里的“对象”

“箭头”学名叫做“态射”。

Arrows as Functions - 箭头作为函数

Arrows also called morphisms, as functions.

可以把函数想象成箭头。假定有一函数f接受一个A类型的值，返回一个B类型的值；此外还有函数g接受B类型的值返回C类型的值。把f的返回值传给g，这样就完成了复合。

比如Unix系统中的管道ls | grep xxx，就是把前者的值作为输入传到后面。

数学中，用g ∘ f来表示函数的复合（注意顺序，复合是从右向左发生的，λx.g(f(x))，可以读作“g after f”）。编程语言中有的直接提供了操作符，例如Haskell 中的.（g . f从右向左）；F#中的>> <<（f >> g g << f前者从左向右复合，后者从右向左）。有些语言没有直接操作符支持，可以动手写出函数体形如g(f(x))，借助x进行函数复合。

1
2
3
4


f :: A -> B
g :: B -> C

g . f :: A -> C

$g \circ f = \lambda x.g \lparen f \lparen x \rparen \rparen$

Properties of Composition - 复合的性质

复合是可结合的。（结合律）

Composition is associative.

1

h ∘ g ∘ f = h ∘ (g ∘ f) = (h ∘ g) ∘ f

$h \circ \lparen g \circ f \rparen$ = $\lparen h \circ g \rparen \circ f$ = $h \circ g \circ f$

1
2
3
4
5
6


f :: A -> B
g :: B -> C
h :: C -> D

-- equality is not defined for functions
h . (g . f) == (h . g) . f == h . g . f

任一对象A，都有一个箭头，它是符合的最小单位。这个箭头从对象出发又指向对象自身。（恒等态射）

这称为$id_A$（identity on A）。在数学定义里，现有f接受A返回B，那么$f \circ id_A = f$，$id_B \circ f = f$。

在编程语言中，可以这么实现T id(T x) { return x; }，当然这里的T一般是个泛型参数，也免得为每个对象都实现一个恒等态射了。

For every object A there is an arrow which is a unit of composition.

This arrow loops from the object to itself. The unit arrow for object A is called $\bold{id} _{A}$ (identity on $A$).

In math notation, if $f$ goes from $A$ to $B$, then $f \circ \bold{id} _A = f$ and $\bold{id} _B \circ f = f$

1
2
3
4
5


id :: a -> a
id x = x

f . id == f
id . f == f

A category consists of objects and arrows (morphisms). Arrows can be composed, and the composition is associative. Every object has an identity arrow that servers as unit under composition.

Composition is the Essence of Programming - 复合是编程的本质

Challenges

Implement the identity function

1
2


// there is an `id` in F#
let idm x = x

Implement the composition function

1
2
3
4
5


// right to left
let compose g f x = g(f(x))

// in F#, there is an `>>` , compose functions left to right
let compose f g x = g(f(x))

test composition function

1
2
3
4
5


let f (i: int): string = string i

compose idm f

compose f idm

1.1 Category: The Essence of Composition - 范畴：复合的本质